链表专题4 - leetcode61. Rotate List/143. Reorder List

61. Rotate List

题目描述

Given a linked list, rotate the list to the right by k places, where k is non-negative.

例子

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL

Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

解法

• 第一次遍历，记录链表长度size
• 有k%size个结点翻转到了前面

解法
记录长度，两次遍历 - (先把链表连成环)

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

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        # Mark size and tail
        size = 1
        tail = head
        while tail.next:
            tail = tail.next
            size += 1
        tail.next = head
        
        # Rotate
        k = k % size
        p = head
        for _ in range(size-k-1):
            p = p.next
        node = p.next
        p.next = None
        return node    
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

143. Reorder List

题目描述

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

例子
Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

解法
法1 - split得到后半段(通过快慢指针)→反转后半段→merge
法2 - 建立辅助数组，存储所有结点后再操作

解法1
时间复杂度O(n)，空间复杂度O(1)

# 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: void Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return
        
        # Split - find the 2nd-half
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        node = slow.next
        slow.next = None
        
        # Reverse the 2nd-half
        node = self.reverseList(node) 
        
        # Merge head and node
        p = head
        while p.next:
            temp = node.next
            node.next = p.next
            p.next = node
            
            p = node.next
            node = temp
        p.next = node
     
    def reverseList(self, head):
        if not head or not head.next:
            return head
        node = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return node
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

解法2
时间复杂度O(n)，空间复杂度O(n)

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        arr = []
        while head:
            arr.append(head)
            head = head.next
        size = len(arr)
        for i in range(size//2):
            arr[i].next = arr[-i]
            arr[-i].next = arr[i+1]
        arr[size//2+1].next = None
            
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16