143. 重排链表(Medium)

题目描述

Leetcode 地址

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-/1→L2→Ln-2→…

样例

Input: 1->2->3->4
Output: 1->4->2->3

解题思路

快慢指针找中点 + 翻转

1->2->3->4->5 # 找中点
1->2->3  4->5 # 切割
1->2->3  5->4 # 随意翻转一个
1->5->2->4->3 # <-- Output

图解

代码

class Solution:
    def reorderList(self, head: ListNode) -> None:
        def findMiddle(head):
            slow, fast = head, head.next
            while fast and fast.next:
                slow = slow.next 
                fast = fast.next.next 
            mid = slow.next 
            slow.next = None 
            return mid 
        def reverse(head):
            pre, cur = None, head
            while cur:
                cur_next_bak = cur.next 
                cur.next = pre 
                pre = cur
                cur = cur_next_bak 
            return pre
        
        def mergeTwoList(l1, l2):
            dummyHead = ListNode(None)
            p = dummyHead
            while l1 and l2:
                p.next = l1
                p = p.next 
                l1 = l1.next 
                p.next = l2
                p = p.next 
                l2 = l2.next 
            p.next = l1 if l1 else l2 
            return dummyHead.next 
                 
        if not head or not head.next: return head 
        l1, l2 = head, findMiddle(head)
        l2 = reverse(l2)
        return mergeTwoList(l1, l2)