Linked List

Core algorithms

1. Reverse a linked list

Iterative Reversing a Linked List

public ListNode reverse(ListNode node) {
    ListNode cur = node;
    ListNode prev = null, next = null;
    while (cur != null) {
        next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

Recursive Reversing a Linked List

I will go over some other ways to reverse a linked list. Would the following way work?

private ListNode prev;
public ListNode reverseList(ListNode cur) {
    if (cur == null) return cur;
    if (cur.next == null) return cur;
    ListNode next = cur.next;
    cur.next = prev;
    prev = cur;
    return reverseList(next);
}

The following way is a fix for the above way.

public ListNode reverseList(ListNode cur) {
    if (cur == null) return cur;
    ListNode next = cur.next;
    cur.next = prev;
    prev = cur;
    if (next == null) return cur;
    return reverseList(next);
}

Another recursive method

• It changes the next point to null at first and on the way up, the next pointer points to the correct node.

public ListNode reverseList(ListNode cur) { // somebody else
    if (cur == null) return null;
    if (cur.next == null) return cur;
    ListNode next = cur.next;
    ListNode last = reverseList(cur.next);
    next.next = cur;
    cur.next = null;
    return last;
}

The same logic as above but slightly different and confusing code.

public ListNode reverseList(ListNode cur) {
    if (cur == null) return null;
    if (cur.next == null) return cur;
    ListNode last = reverseList(cur.next);
    cur.next.next = cur;
    cur.next = null;
    return last;
}

2. cycle detection - slow/fast pointer (https://www.geeksforgeeks.org/how-does-floyds-slow-and-fast-pointers-approach-work/)

public boolean detectLoop(ListNode node) {
    ListNode slow = node, fast = node;
    while(fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Reverse linked list

• https://leetcode.com/problems/reverse-linked-list/
• https://leetcode.com/problems/reverse-linked-list-ii/
• https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Two-pass

• cur should fall to the node to be deleted except when cur is the first node because that's the only case the logic changes.
• Let the counter go where the 0th point is the last to stop and that's where the cur will land and that's the out of the bounds of the count.
• Note that without counting in the beginning, you can't modify the node and count how many nodes are there at the same time.

public ListNode removeNthFromEnd(ListNode cur, int n) {
    int count = getCount(cur);
    n = count - n;
    if (n == 0) return cur.next;
    ListNode head = cur, prev = null;
    while (n-- != 0) {
        prev = cur;
        cur = cur.next;
    }
    prev.next = cur.next;
    return head;
}
private int getCount(ListNode head) {
    // return how many nodes are there
    if (head == null) return 0;
    return getCount(head.next) + 1;
}

One-pass

public ListNode removeNthFromEnd(ListNode cur, int n) {
    ListNode dummy = new ListNode(0), first = dummy, second = dummy;
    dummy.next = cur;

    // Advance the first pointer
    for (int i = 0; i <= n; i++) {
        first = first.next;
    }

    // Move first to the end and move the second too while maintaining the gap
    // second pointer points to the node one before the node to be deleted.
    while (first != null) {
        first = first.next;
        second = second.next;
    }

    second.next = second.next.next;

    return dummy.next;
}

Slow/fast pointer

• https://leetcode.com/problems/middle-of-the-linked-list/

public ListNode middleNode(ListNode node) {
    ListNode fast = node, slow = node;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
} 

• https://leetcode.com/problems/linked-list-cycle/

public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    ListNode dummy = new ListNode(0); dummy.next = head;
    ListNode slow = dummy, fast = dummy;
    slow = slow.next; fast = fast.next.next;
    while (fast != null && fast.next != null) {
        if (slow == fast) return true;
        slow = slow.next;
        fast = fast.next.next;
    }
    return false;
} 

• https://leetcode.com/problems/palindrome-linked-list/
• TODO: do the palindrome question with slow/fast pointer

Reorder list

• https://leetcode.com/problems/merge-two-sorted-lists

public ListNode mergeTwoLists(ListNode one, ListNode two) {
    if (one == null && two == null) return one;
    else if (one == null) return two;
    else if (two == null) return one;

    ListNode head = one.val < two.val ? one : two;
    ListNode prev = null, cur = null;
    while (one != null && two != null) {
        if (one.val < two.val) {
            cur = one;
            one = one.next;
        } else {
            cur = two;
            two = two.next;
        }
        if (prev != null) {
            prev.next = cur;
        }
        prev = cur;
    }
    prev.next = one != null ? one : two; // two can be null and it's fine to be added at the end

    return head;
} 

public ListNode mergeTwoLists(ListNode one, ListNode two) {
    if (one == null && two == null) return null;
    else if (one == null) return two; 
    else if (two == null) return one;

    if (one.val < two.val) {
        one.next = mergeTwoLists(one.next, two);
        return one;
    } else {
        two.next = mergeTwoLists(one, two.next);
        return two;
    }
}

• https://leetcode.com/problems/reorder-list/

• https://leetcode.com/problems/odd-even-linked-list/