LeetCode 143. 重排链表

题目

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

例：
输入：head = [1,2,3,4]
输出：[1,4,2,3]

方法：翻转后半部分链表

思路同 234. 回文链表，区别在于本题在翻转链表后进行插入

• slow 表示慢指针，每次向右移动一步；fast 表示快指针，每次向右移动两步。直至快指针 fast 或快指针向右移动一步 fast.next 后不存在，即当快指针 fast 指向链表尾部或尾部的下一个位置时，循环停止。那么此时，慢指针指向中部

  
  
• right 指向后半部分链表的首部，即需要进行翻转部分的首部，初始值为慢指针的下一个节点 slow.next
• left 指向前半部分链表的首部，并将其前半部分尾部 slow.next 指向的节点设为 None，从而使得原链表正式分成两个链表
• 对第二个链表进行翻转操作
• 循环，因为第二个链表一定比第一个链表短，所以通过第二个链表来判断循环的停止
  • curLeft 指向第一个链表的当前指向节点的下一个节点，为了进行插入操作；curRight 指向第二个链表的当前指向节点的下一个节点，为了进行插入操作

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reorderList(self, head):
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        right = slow.next
        slow.next = None
        left = head
        right = self.reverse(right)

        while right:
            curLeft = left.next
            left.next = right
            left = curLeft

            curRight = right.next
            right.next = left
            right = curRight
        return head
    
    def reverse(self, node):
        pre = None
        while node:
            temp = node.next
            node.next = pre
            pre = node
            node = temp
        return pre

参考

代码相关：https://programmercarl.com/0143.%E9%87%8D%E6%8E%92%E9%93%BE%E8%A1%A8.html