重排链表

问题简述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
    L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
    L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路1

找中间节点；
将第二段链表反转；
然后合并两段链表；

细节:
- 因为需要截断, 所以实际上找的是中间节点的前一个节点(偶数情况下)

Python

# 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: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """

        def reverse(h):
            pre, cur = None, h
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            return pre
        
        def get_mid(h):
            slow, fast = h, h.next  # 找中间节点的前一个节点
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        
        mid = get_mid(head)
        tmp = mid.next
        mid.next = None  # 截断
        mid = reverse(tmp)

        l, r = head, mid
        while r:  # len(l) >= len(r)
            l_nxt, r_nxt = l.next, r.next
            l.next, r.next = r, l_nxt  # 关键步骤: 将 r 接入 l
            l, r = l_nxt, r_nxt

思路2

把节点存入列表;
通过索引拼接节点;

细节:
- 把节点存入数组后, 可以使用下标访问节点, 形如 arr[i].next = ...
- 拼接节点时注意边界位置的操作;
- 尾节点的截断;

Python

# 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: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        tmp = []
        cur = head
        while cur:
            tmp.append(cur)
            cur = cur.next
        
        l, r = 0, len(tmp) - 1
        while l < r:  # 退出循环时 l == r
            tmp[l].next = tmp[r]
            l += 1
            if l == r: break  # 易错点
            tmp[r].next = tmp[l]
            r -= 1

        # 退出循环时 l 刚好指在中间节点(奇数时), 或中间位置的下一个节点(偶数时)
        tmp[l].next = None  # 易错点

Previous买卖股票的最佳时机III Next乘积最大子数组

Last updated 2 years ago

给定一个单链表 L 的头节点 head ，单链表 L 表示为： L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为： L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

# 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: Optional[ListNode]) -> None: """ Do not return anything, modify head in-place instead. """ def reverse(h): pre, cur = None, h while cur: nxt = cur.next cur.next = pre pre = cur cur = nxt return pre def get_mid(h): slow, fast = h, h.next # 找中间节点的前一个节点 while fast and fast.next: slow = slow.next fast = fast.next.next return slow mid = get_mid(head) tmp = mid.next mid.next = None # 截断 mid = reverse(tmp) l, r = head, mid while r: # len(l) >= len(r) l_nxt, r_nxt = l.next, r.next l.next, r.next = r, l_nxt # 关键步骤: 将 r 接入 l l, r = l_nxt, r_nxt

# 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: Optional[ListNode]) -> None: """ Do not return anything, modify head in-place instead. """ tmp = [] cur = head while cur: tmp.append(cur) cur = cur.next l, r = 0, len(tmp) - 1 while l < r: # 退出循环时 l == r tmp[l].next = tmp[r] l += 1 if l == r: break # 易错点 tmp[r].next = tmp[l] r -= 1 # 退出循环时 l 刚好指在中间节点(奇数时), 或中间位置的下一个节点(偶数时) tmp[l].next = None # 易错点