【力扣143. 重排链表】寻找链表中点 + 链表逆序 + 合并链表（python3）

题目描述

https://leetcode-cn.com/problems/reorder-list/
这个题还能顺便练习寻找链表中点 + 链表逆序

思路题解

方法二：寻找链表中点 + 链表逆序 + 合并链表
注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。
这样我们的任务即可划分为三步：

• 找到原链表的中点（参考「876. 链表的中间结点」）。我们可以使用快慢指针来 O(N) 地找到链表的中间节点。
• 将原链表的右半端反转（参考「206. 反转链表」）。我们可以使用迭代法实现链表的反转。
• 将原链表的两端合并。因为两链表长度相差不超过 1，因此直接合并即可。

自己写的代码：

# 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.
        """
        def reverseList(start):
            if not start or not start.next:return 
            l,m,r=start,start.next,start.next.next
            l.next=None
            while r:
                m.next=l
                l=m
                m=r
                r=r.next
            m.next=l
            return m
        if not head or not head.next or not head.next.next:return
        start,end=head,head
        while end.next.next:
            start=start.next
            end=end.next.next
            if not end.next:break
            if not end.next.next:
                start,end=start.next,end.next
                break
        j=reverseList(start)
        # print(start.val,end.val)
        i=head
        while i!=j and i.next!=j:
            # print(i.val,j.val,head)
            tmp=j
            j=j.next
            tmp.next=i.next
            i.next=tmp
            i=i.next.next
        return 
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

官方题解代码：
两个代码时间时间空间一样，都是On O1

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return
        
        mid = self.middleNode(head)
        l1 = head
        l2 = mid.next
        mid.next = None
        l2 = self.reverseList(l2)
        self.mergeList(l1, l2)
    
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            nextTemp = curr.next
            curr.next = prev
            prev = curr
            curr = nextTemp
        return prev

    def mergeList(self, l1: ListNode, l2: ListNode):
        while l1 and l2:
            l1_tmp = l1.next
            l2_tmp = l2.next

            l1.next = l2
            l1 = l1_tmp

            l2.next = l1
            l2 = l2_tmp

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