Question

Formatted question description: https://leetcode.ca/all/148.html

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

Constraints:

The number of nodes in the list is in the range [0, 5 * 10⁴].
-10⁵ <= Node.val <= 10⁵

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Algorithm

The title limits the time to be O(nlgn). Only

quick sort,
merge sort, and
heap sort

meet the requirements. According to the characteristics of singly linked lists, merge sort is most suitable.

To do merge sort, the middle node of the list should be found.

Use two pointers to find the middle node. Each time the fast pointer moves two steps and the slow pointer moves one step.
When the fast pointer moves to the end, the slow pointer points the middle node.
After finding the middle node, do merge sort for two parts of the node respectively, and merge the two parts after both parts are sorted.

Two merge two parts of a list, always find the node with the smallest number each time and append the node to the sorted list.

Code

public class Sort_List {

    public class Solution {
        /**
         * Definition for singly-linked list.
         * class ListNode {
         * int val;
         * ListNode next;
         * ListNode(int x) {
         * val = x;
         * next = null;
         * }
         * }
         */

        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;

            ListNode dummy = new ListNode(0);
            dummy.next = head;

            ListNode prev = dummy;
            ListNode slow = head;
            ListNode fast = head;

            // 每次都要找中点，复杂度略高啊
            while (fast != null && fast.next != null) {
                prev = slow;
                slow = slow.next;
                fast = fast.next.next;
            }

            ListNode left = head; // eg. [1,2]
            ListNode right = slow;
            prev.next = null; // cut

            ListNode sortedLeft = sortList(left);
            ListNode sortedRight = sortList(right);

            return mergeSorted(sortedLeft, sortedRight);
        }

        public ListNode mergeSorted(ListNode left, ListNode right) {
            ListNode dummy = new ListNode(0);

            ListNode current = dummy;

            while (left != null || right != null) {
                int lval = left == null ? Integer.MAX_VALUE : left.val;
                int rval = right == null ? Integer.MAX_VALUE : right.val;

                if (lval < rval) {
                    current.next = new ListNode(lval);
                    left = left.next; // I missed this...
                } else {
                    current.next = new ListNode(rval);
                    right = right.next;
                }

                current = current.next;
            }

            return dummy.next;
        }
    }


    // constant extra space using Bottom Up Approach
    class Solution_bottom_up_merge_sort {
        ListNode tail = new ListNode(0);
        ListNode nextSubList = new ListNode(0);

        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null)
                return head;
            int n = getCount(head);
            ListNode start = head;
            ListNode dummyHead = new ListNode(0);
            for (int size = 1; size < n; size = size * 2) {
                tail = dummyHead;
                while (start != null) {
                    if (start.next == null) {
                        tail.next = start;
                        break;
                    }
                    ListNode mid = split(start, size);
                    merge(start, mid);
                    start = nextSubList;
                }
                start = dummyHead.next;
            }
            return dummyHead.next;
        }

        ListNode split(ListNode start, int size) {
            ListNode midPrev = start;
            ListNode end = start.next;
            //use fast and slow approach to find middle and end of second linked list
            for (int index = 1; index < size && (midPrev.next != null || end.next != null); index++) {
                if (end.next != null) {
                    end = (end.next.next != null) ? end.next.next : end.next;
                }
                if (midPrev.next != null) {
                    midPrev = midPrev.next;
                }
            }
            ListNode mid = midPrev.next;
            midPrev.next = null;
            nextSubList = end.next;
            end.next = null;
            // return the start of second linked list
            return mid;
        }

        void merge(ListNode list1, ListNode list2) {
            ListNode dummyHead = new ListNode(0);
            ListNode newTail = dummyHead;
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    newTail.next = list1;
                    list1 = list1.next;
                    newTail = newTail.next;
                } else {
                    newTail.next = list2;
                    list2 = list2.next;
                    newTail = newTail.next;
                }
            }
            newTail.next = (list1 != null) ? list1 : list2;
            // traverse till the end of merged list to get the newTail
            while (newTail.next != null) {
                newTail = newTail.next;
            }
            // link the old tail with the head of merged list
            tail.next = dummyHead.next;
            // update the old tail to the new tail of merged list
            tail = newTail;
        }

        int getCount(ListNode head) {
            int cnt = 0;
            ListNode ptr = head;
            while (ptr != null) {
                ptr = ptr.next;
                cnt++;
            }
            return cnt;
        }
    }

}

############

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode t = slow.next;
        slow.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(t);
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
}

// OJ: https://leetcode.com/problems/sort-list/
// Time: O(NlogN)
// Space: O(logN)
class Solution {
    ListNode* splitList(ListNode *head) {
        ListNode dummy, *p = &dummy, *q = &dummy;
        dummy.next = head;
        while (q && q->next) {
            q = q->next->next;
            p = p->next;
        }
        auto next = p->next;
        p->next = NULL;
        return next;
    }
    ListNode *mergeList(ListNode *a, ListNode *b) {
        ListNode head, *tail = &head;
        while (a && b) {
            ListNode *node;
            if (a->val <= b->val) {
                node = a;
                a = a->next;
            } else {
                node = b;
                b = b->next;
            }
            tail->next = node;
            tail = node;
        }
        if (a) tail->next = a;
        if (b) tail->next = b;
        return head.next;
    }
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        auto b = splitList(head);
        return mergeList(sortList(head), sortList(b));
    }
};

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        t = slow.next
        slow.next = None
        l1, l2 = self.sortList(head), self.sortList(t)
        dummy = ListNode()
        cur = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next

############

# 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 head:
      fast = slow = head
      pre = None

      while fast and fast.next:
        pre = slow
        slow = slow.next
        fast = fast.next.next

      if not pre:
        return head
      pre.next = None

      left = self.sortList(head)
      right = self.sortList(slow)

      p = dummy = ListNode(-1)
      while left and right:
        if left.val < right.val:
          p.next = left
          left = left.next
        else:
          p.next = right
          right = right.next
        p = p.next

      if left:
        p.next = left
      if right:
        p.next = right
      return dummy.next

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	slow, fast := head, head.Next
	for fast != nil && fast.Next != nil {
		slow, fast = slow.Next, fast.Next.Next
	}
	t := slow.Next
	slow.Next = nil
	l1, l2 := sortList(head), sortList(t)
	dummy := &ListNode{}
	cur := dummy
	for l1 != nil && l2 != nil {
		if l1.Val <= l2.Val {
			cur.Next = l1
			l1 = l1.Next
		} else {
			cur.Next = l2
			l2 = l2.Next
		}
		cur = cur.Next
	}
	if l1 != nil {
		cur.Next = l1
	} else {
		cur.Next = l2
	}
	return dummy.Next
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function sortList(head: ListNode | null): ListNode | null {
    if (head == null || head.next == null) return head;
    // 快慢指针定位中点
    let slow: ListNode = head,
        fast: ListNode = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 归并排序
    let mid: ListNode = slow.next;
    slow.next = null;
    let l1: ListNode = sortList(head);
    let l2: ListNode = sortList(mid);
    let dummy: ListNode = new ListNode();
    let cur: ListNode = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = l1 == null ? l2 : l1;
    return dummy.next;
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
    if (!head || !head.next) {
        return head;
    }
    let slow = head;
    let fast = head.next;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let t = slow.next;
    slow.next = null;
    let l1 = sortList(head);
    let l2 = sortList(t);
    const dummy = new ListNode();
    let cur = dummy;
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = l1 || l2;
    return dummy.next;
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode SortList(ListNode head) {
        if (head == null || head.next == null)
        {
            return head;
        }
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode t = slow.next;
        slow.next = null;
        ListNode l1 = SortList(head);
        ListNode l2 = SortList(t);
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (l1 != null && l2 != null)
        {
            if (l1.val <= l2.val)
            {
                cur.next = l1;
                l1 = l1.next;
            }
            else
            {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
}

148 - Sort List

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions