148 Sort List

https://leetcode.com/problems/sort-list/

solution

• 快排

时间复杂度：O() 空间复杂度：O()

• 归并排序

# https://www.geeksforgeeks.org/merge-sort-for-linked-list/?ref=lbp

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        # Split the list into two halves
        left = head
        right = self.getMid(head)
        tmp = right.next
        right.next = None
        right = tmp
        
        left = self.sortList(left)
        right = self.sortList(right)
        
        return self.merge(left, right)
    
    def getMid(self, head):
        slow = head
        fast = head.next
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    # Merge the list
    def merge(self, list1, list2):
        newHead = tail = ListNode()
        while list1 and list2:
            if list1.val > list2.val:
                tail.next = list2
                list2 = list2.next
            else:
                tail.next = list1
                list1 = list1.next
            tail = tail.next
        
        if list1:
            tail.next = list1
        if list2:
            tail.next = list2
        
        return newHead.next

时间复杂度：O() 空间复杂度：O()

follow up

143. Reorder List

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        node_list = []
        while head:
            node_list.append(head)
            head = head.next
        
        l = 0
        r = len(node_list) - 1
        last = head
        while l < r:
            node_list[l].next = node_list[r]
            l += 1

            if l == r:  # 注意整体中last的使用
                last = node_list[r]
                break

            node_list[r].next = node_list[l]
            r -= 1

            last = node_list[l]
        
        if last:
            last.next = None

class Solution:
    def reorderList(self, head):
        # step 1: find middle
        if not head: 
            return []
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        # step 2: reverse second half
        prev, curr = None, slow.next
        while curr:
            nextt = curr.next
            curr.next = prev
            prev = curr
            curr = nextt    
        slow.next = None
        
        # step 3: merge lists
        head1, head2 = head, prev
        while head2:
            nextt = head1.next
            head1.next = head2
            head1 = head2
            head2 = nextt

86. Partition List

# 顺便回忆一下快排中的partition

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        dummy_before = ListNode(0)
        dummy_after = ListNode(0)

        before = dummy_before
        after = dummy_after

        while head:
            if head.val < x:
                before.next = head
                before = head
            else:
                after.next = head
                after = head
            head = head.next  # 注意几个指针的移动
        
        after.next = None
        before.next = dummy_after.next
        return dummy_before.next

61. Rotate List

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return None
            
        dummy = ListNode(-1)
        length = 0
        tail = None
        ori_head = head

        while head and head.next:
            length += 1
            head = head.next
        
        length += 1
        tail = head
        tail.next = ori_head

        k = k % length
        head = ori_head
        for i in range(length - k - 1):
            head = head.next
        
        dummy.next = head.next
        head.next = None
        return dummy.next

Sorted insert for circular linked list