AUG!!! If you have to sort a linked list, sort it in a clean way, JAVA, merge sort with comment.


  • 0
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode sortList(ListNode head) {
            if(head == null || head.next == null)
                return head;
            ListNode slower = head;
            ListNode faster = head;
            ListNode previous = new ListNode(0);
            previous.next = slower;
    // use previous node to keep tracking slower node, because we are going to change the tail of the first half list into null;
            while(faster != null && faster.next != null){
                previous = previous.next;
                slower = slower.next;
                faster = faster.next.next;
            }
            ListNode secondHalf = sortList(slower);
            previous.next = null;//this cut the list into half;
            ListNode firstHalf = sortList(head);
            return merge(firstHalf, secondHalf);
        }
        public ListNode merge(ListNode node1, ListNode node2){
            if(node1 == null)   return node2;
            if(node2 == null)   return node1;
            ListNode runningNode1 = node1;
            ListNode runningNode2 = node2;
    // What we are going to do here is to constructe a full sorted linked list using nodes of those two sorted list one by one.
            ListNode helper = new ListNode(0);// this helps us to track the head of final sorted list.
            ListNode copy = helper;
            while(runningNode1 != null && runningNode2 != null){
    // Compare nodes one by one, put them into the correct position until we reach the tail of any list's tail.
                if(runningNode1.val > runningNode2.val){
                    copy.next = runningNode2;
                    copy = copy.next;
                    runningNode2 = runningNode2.next;
                }else{
                    copy.next = runningNode1;
                    copy = copy.next;
                    runningNode1 = runningNode1.next;
                }
            }
    // Connect the remains with the sorted list and return final result;
            if(runningNode1 == null)
                copy.next = runningNode2;
            else
                copy.next = runningNode1;
            return helper.next;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.