Pretty Sure

LeetCode - Split Linked List in Parts

Question Definition

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list “parts”.

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode’s representing the linked list parts that are formed.

Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]

LeetCode - Split Array into Consecutive Subsequences

Question Definition

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

LeetCode - Sort List

Question Definition

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

LeetCode - Reverse Linked List II

Question Definition

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:

Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Java Solution

public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode cur = dummy;
    ListNode pre = null;
    ListNode front = null;
    ListNode last = null;
    for (int i = 1; i <= m - 1; ++i) cur = cur.next;
    pre = cur;
    last = cur.next;
    for (int i = m; i <= n; ++i) {
        cur = pre.next;
        pre.next = cur.next;
        cur.next = front;
        front = cur;
    }
    cur = pre.next;
    pre.next = front;
    last.next = cur;
    return dummy.next;
}

LeetCode - Remove Duplicates from Sorted List II

Question Definition

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.