【LeetCode】148. Sort linked list

1 subject

2 thought

Divide the linked list into two , Then flip the linked list in the second half , Cross merge the two linked lists after flipping . These operations are relatively simple , But together , It may take a little time to write .

3 Code

# 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. """
        mid = self.splitList(head)
        #  take  mid  The first part of the list is flipped 
        head2 = self.reverseList(mid)
        return self.mergeList(head,head2)
        

    #  Binary linked list 
    def splitList(self,head):
        slow = fast = head
        while(fast.next and fast.next.next):
            fast = fast.next.next
            slow = slow.next
        tmp = slow.next
        slow.next = None
        return tmp
    
    #  Flip list 
    def reverseList(self,head):
        pre = None
        start = head
        while(start):
            tmp = start.next 
            start.next = pre
            pre = start
            start = tmp        
        return pre

    #  Cross merger 
    def mergeList(self,head1,head2):
        cnt = 0         
        tail = head = head1 #  Last returned header node 
        head1 = head1.next 
        while(head1 and head2):
            if cnt % 2 == 0:
               tail.next = head2
               head2 = head2.next
            else:
                tail.next = head1
                head1 = head1.next
            tail = tail.next
            cnt += 1
        if head1:
            tail.next = head1
        if head2:
            tail.next = head2
        return head