LeetCode-143-重排链表

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

image.png
解题思路：

1. 用快慢指针将链表分为两部分；
2. 将后半部分链表翻转；
3. 交叉合并两个链表。

Python3代码：

# 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:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return head
        fast = head 
        slow = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        mid = slow
        l1 = head
        l2 = mid.next
        mid.next = None
        
        def reverseList(head: ListNode) -> ListNode:
            prev = None
            curr = head
            while curr:
                nextTemp = curr.next
                curr.next = prev
                prev = curr
                curr = nextTemp
            return prev

        l2 = reverseList(l2)
        while l1 and l2:
            l1_tmp = l1.next 
            l2_tmp = l2.next
            
            l1.next = l2
            l1 = l1_tmp
            
            l2.next = l1
            l2 = l2_tmp