给定一个单链表 L
的头节点 head
,单链表 L
表示为:
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为:
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
输入: head = [1,2,3,4] 输出: [1,4,2,3]
示例 2:
输入: head = [1,2,3,4,5] 输出: [1,5,2,4,3]
提示:
- 链表的长度范围为
[1, 5 * 104]
1 <= node.val <= 1000
注意:本题与主站 143 题相同:https://leetcode.cn/problems/reorder-list/
相当于这 3 道问题,只需要 5 行代码将它们组合:
# 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:
mid = self.middleNode(head)
tmp = mid.next
mid.next = None
tmp = self.reverseList(tmp)
head = self.mergeTwoLists(head, tmp)
def middleNode(self, head: ListNode) -> ListNode:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseList(self, head: ListNode) -> ListNode:
pre, cur = None, head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode()
cur = dummy
while l1 and l2:
cur.next = l1
l1 = l1.next
cur = cur.next
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
/**
* 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 tmp = mid.next;
mid.next = null;
tmp = reverseList(tmp);
head = mergeTwoLists(head, tmp);
}
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;
}
private ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (l1 != null && l2 != null) {
cur.next = l1;
l1 = l1.next;
cur = cur.next;
cur.next = l2;
l2 = l2.next;
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return dummy.next;
}
}
/**
* 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) {
ListNode* mid = middleNode(head);
ListNode* tmp = mid->next;
mid->next = nullptr;
tmp = reverseList(tmp);
head = mergeTwoLists(head, tmp);
}
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode();
ListNode* cur = dummy;
while (l1 && l2) {
cur->next = l1;
l1 = l1->next;
cur = cur->next;
cur->next = l2;
l2 = l2->next;
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return dummy->next;
}
};
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reorderList(head *ListNode) {
mid := middleNode(head)
tmp := mid.Next
mid.Next = nil
tmp = reverseList(tmp)
head = mergeTwoLists(head, tmp)
}
func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
cur := head
for cur != nil {
tmp := cur.Next
cur.Next = pre
pre = cur
cur = tmp
}
return pre
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := new(ListNode)
cur := dummy
for l1 != nil && l2 != nil {
cur.Next = l1
l1 = l1.Next
cur = cur.Next
cur.Next = l2
l2 = l2.Next
cur = cur.Next
}
if l1 != nil {
cur.Next = l1
}
if l2 != nil {
cur.Next = l2
}
return dummy.Next
}