leetcode 143. Reorder List （链表重构顺序）_leetcode重构链表

题目要求

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

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解题思路

这道题很有价值，涉及到了链表的多项操作，真正的是一道顶三道，建议多练习几遍。猛的一看这道题真的是没什么思路啊！如何在链表进行每个孔插入一个节点？这是个问题，但是当你有了这个思想的时候，你就已经准备打开成功的大门了，你可以把它理解为两个链表合并的工作。再仔细相信好像是两个链表，一个是原链表的前部分，一个是后半部分。但是后半部分的链表怎么顺序反过来了？为了解决这个问题，我们还要加上一个反转链表的操作。按这个思路想下来，我们发现做这道题需要三个步骤：
（1）将链表分为左右的两个部分（快慢指针实现）
（2）反转后半部分的链表（三指针实现）
（3）合并两个链表（傀儡节点实现，每次要合并两个点）
综上步骤，你就可以解出答案了，现在想想看是不是觉得这道题很超值？好几个知识点都复习到了

主要代码python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        # @找中点
        def findmid(head):
            fast = head
            slow = head
            while fast is not None and fast.next is not None:
                fast = fast.next.next
                slow = slow.next
            return slow
        # @反转后半段链表  
        def reversel2(head):
            pre = None
            while head is not None:
                nex = head.next
                head.next = pre
                pre = head
                head = nex
            return pre
        if head is None:
            return None
        l1 =findmid(head)
        l2 = l1.next # 构建了后半部分链表
        l1.next = None # 将前后链表分开
        l1 = head
        l2 = reversel2(l2)
         # @合并过程
        dummy = ListNode(0)
        tail = dummy
        while l1 is not None and l2 is not None:
            # tmp = l1.next # 存放下一个节点
            tail.next = l1 # 开始合并1
            l1 = l1.next
            tail.next.next = l2 # 开始合并2
            l2 = l2.next
            tail = tail.next.next # 每次都是移动两个步长继续合并
        tail.next = (l1 if l1 is not None else l2) # 不要忘了这一步
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

原题链接 https://leetcode-cn.com/problems/reorder-list/