上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
}
};
javascript 解法, 执行用时: 92 ms, 内存消耗: 48.6 MB, 提交时间: 2023-07-31 09:21:32
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function (head) {
// 876. 链表的中间结点
function middleNode(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 206. 反转链表
function reverseList(head) {
let pre = null, cur = head;
while (cur) {
const nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
const mid = middleNode(head);
let head2 = reverseList(mid);
while (head2.next != null) {
const nxt = head.next;
const nxt2 = head2.next;
head.next = head2;
head2.next = nxt;
head = nxt;
head2 = nxt2;
}
};
golang 解法, 执行用时: 12 ms, 内存消耗: 5.1 MB, 提交时间: 2023-07-31 09:21:16
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// 876. 链表的中间结点
func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
// 206. 反转链表
func reverseList(head *ListNode) *ListNode {
var pre, cur *ListNode = nil, head
for cur != nil {
nxt := cur.Next
cur.Next = pre
pre = cur
cur = nxt
}
return pre
}
func reorderList(head *ListNode) {
mid := middleNode(head)
head2 := reverseList(mid)
for head2.Next != nil {
nxt := head.Next
nxt2 := head2.Next
head.Next = head2
head2.Next = nxt
head = nxt
head2 = nxt2
}
}
java 解法, 执行用时: 1 ms, 内存消耗: 44.6 MB, 提交时间: 2023-07-31 09:20:59
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
ListNode mid = middleNode(head);
ListNode head2 = reverseList(mid);
while (head2.next != null) {
ListNode nxt = head.next;
ListNode nxt2 = head2.next;
head.next = head2;
head2.next = nxt;
head = nxt;
head2 = nxt2;
}
}
// 876. 链表的中间结点
private ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 206. 反转链表
private ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
}
python3 解法, 执行用时: 76 ms, 内存消耗: 24.8 MB, 提交时间: 2023-07-31 09:20:19
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
# 876. 链表的中间结点
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 206. 反转链表
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre, cur = None, head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
def reorderList(self, head: Optional[ListNode]) -> None:
mid = self.middleNode(head)
head2 = self.reverseList(mid)
while head2.next:
nxt = head.next
nxt2 = head2.next
head.next = head2
head2.next = nxt
head = nxt
head2 = nxt2
cpp 解法, 执行用时: 32 ms, 内存消耗: 17.3 MB, 提交时间: 2023-07-31 09:19:39
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
* 先用快慢双指针的方法找到链表中间节点, 然后反转链表后半部分,
* 再交替地合并链表的两个部分
*/
class Solution {
public:
void reorderList(ListNode *head) {
if (!head->next)
return;
ListNode *mid = find_mid(head);
ListNode *right = reverse(mid->next);
mid->next = nullptr;
head = comb(head, right);
}
private:
ListNode *reverse(ListNode *root) {//反转root为首的链表
ListNode *pre = nullptr;
for (ListNode *next; root; pre = root, root = next) {
next = root->next;
root->next = pre;
}
return pre;
}
ListNode *find_mid(ListNode *head) {//返回链表前半部分的最后一个元素
if (!head->next)
return head;
ListNode *slow = head, *fast = head;
while (1) {
fast = fast->next->next;
if (!fast)
break;
slow = slow->next;
if (!fast->next)
break;
}
return slow;
}
ListNode *comb(ListNode *left, ListNode *right) {//交替地合并两个链表
ListNode *res = new ListNode(), *cur = res;
while (1) {
cur->next = postadd(left);
cur = cur->next;
if (!right) {
cur->next = nullptr;
break;
}
cur->next = postadd(right);
cur = cur->next;
if (!left) {
cur->next = nullptr;
break;
}
}
return res->next;
}
ListNode *postadd(ListNode *&t) {// 返回t, 然后t=t->next
ListNode *res = t;
t = t->next;
return res;
}
};
python3 解法, 执行用时: 72 ms, 内存消耗: 23.3 MB, 提交时间: 2022-08-10 16:07:40
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
if not head:
return
mid = self.middleNode(head)
l1 = head
l2 = mid.next
mid.next = None
l2 = self.reverseList(l2)
self.mergeList(l1, l2)
def middleNode(self, head: ListNode) -> ListNode:
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseList(self, head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
nextTemp = curr.next
curr.next = prev
prev = curr
curr = nextTemp
return prev
def mergeList(self, l1: ListNode, l2: ListNode):
while l1 and l2:
l1_tmp = l1.next
l2_tmp = l2.next
l1.next = l2
l1 = l1_tmp
l2.next = l1
l2 = l2_tmp
