Alibi

My Life is Getting Better

Leetcode[148] Sort List

12 Nov 2015

###Task1 Sort a linked list in O(n log n) time using constant space complexity.

###Python

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

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        if not head.next:
            return head
        dummyLeft = ListNode(0)
        leftHead = dummyLeft
        dummyMid = ListNode(0)
        midHead = dummyMid
        dummyRight = ListNode(0)
        rightHead = dummyRight
        cur = head
        while head:
            if head.val == cur.val:
                midHead.next = head
                midHead = midHead.next
            elif head.val > cur.val:
                rightHead.next = head
                rightHead = rightHead.next
            else:
                leftHead.next = head
                leftHead = leftHead.next
            head = head.next
        leftHead.next = None
        rightHead.next = None
        midHead.next = None
        leftHead = self.sortList(dummyLeft.next)
        rightHead = self.sortList(dummyRight.next)
        
        return self.concate(leftHead, dummyMid.next, rightHead)
    
    def findTail(self, head):
        if not head:
            return head
        while head.next:
            head = head.next
        return head
    
    def concate(self, left, mid, right):
        dummy = ListNode(0)
        head = dummy
        head.next = left
        head = self.findTail(head)
        head.next = mid
        head = self.findTail(head)
        head.next = right
        return dummy.next

###Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    public ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        
        return slow;
    }
    
    public ListNode move2Tail(ListNode head) {
        //every time! if use head.next, check head first
        if (head == null) {
            return head;
        }
        while (head.next != null) {
            head = head.next;
        }
        
        return head;
    }
    
    public ListNode concatenate(ListNode left, ListNode mid, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        
        head.next = left;
        head = move2Tail(head);
        head.next = mid;
        head = move2Tail(head);
        head.next = right;
        
        return dummy.next;
    }
    
    public ListNode sortList(ListNode head) {
        //edge
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode mid = findMiddle(head);
        ListNode dummyLeft = new ListNode(0);
        ListNode tailLeft = dummyLeft;
        ListNode dummyMiddle = new ListNode(0);
        ListNode tailMiddle = dummyMiddle;
        ListNode dummyRight = new ListNode(0);
        ListNode tailRight = dummyRight;
        
        while (head != null) {
            if (head.val < mid.val) {
                tailLeft.next = head;
                tailLeft = tailLeft.next;
            } else if (head.val > mid.val) {
                tailRight.next = head;
                tailRight = tailRight.next;
            } else {
                tailMiddle.next = head;
                tailMiddle = tailMiddle.next;
            }
            
            head = head.next; // forget this line
        }
        tailLeft.next = null;
        tailRight.next = null;
        tailMiddle.next = null;
        
        ListNode left = sortList(dummyLeft.next);
        ListNode right = sortList(dummyRight.next);
        
        return concatenate(left, dummyMiddle.next, right);
    }
}

###Points

Related Posts