Data Structures
    Overview
    Number
    String
    Array
    Linked List
    Stack
    Hash
    Tree
    Trie
    Advanced Data Structure
    Probabilistic Data Structures
    Big O

Algorithm - Linked List

Updated: 2022-02-12

Definition

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

Common Techniques

Fast Runner / Slow Runner

Two pointers, one moves one node at a time, the other moves 2 nodes.

ListNode fast = head;
ListNode slow = head;

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

Dummy Node

Create dummy node before head.

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

Calculate Size

int size = 0;
while (node != null) {
    node = node.next;
    size++;
}

Size can be used in many cases, like "Intersection of Two Linked Lists"

If You Can Not Move The Node, Modify The Value

As in "Delete Node in the Middle of Singly Linked List".

Delete Node in the Middle of Singly Linked List

Copy the value from the next node, and remove the next node. It is effectively the same as removing the current node.

node.val = node.next.val;
node.next = node.next.next;

Intersection of Two Linked Lists

Calculate the sized of the two lists, move the longer list's head forward until the two lists have the same size; then move both heads forward until they are the same node.

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int sizeA = 0, sizeB = 0;
    ListNode ptrA = headA, ptrB = headB;

    while (ptrA != null) {
        ptrA = ptrA.next;
        sizeA++;
    }

    while (ptrB != null) {
        ptrB = ptrB.next;
        sizeB++;
    }

    int diff = sizeA - sizeB;
    if (diff > 0) {
        while (diff-- > 0) {
            headA = headA.next;
        }
    } else {
        while (diff++ < 0) {
            headB = headB.next;
        }
    }

    while (headA != headB) {
        headA = headA.next;
        headB = headB.next;
    }

    return headA;
}

Flatten Binary Tree to Linked List

              1
               \
     1          2
    / \          \
   2   5    =>    3
  / \   \          \
 3   4   6          4
                     \
                      5
                       \
                        6

Recursive:

public void flatten(TreeNode root) {
    if (root == null || root.left == null && root.right == null) {
        return;
    }

    if (root.left != null) {
        flatten(root.left);
        TreeNode tmpRight = root.right;
        root.right = root.left;
        root.left = null;
        TreeNode t = root.right;
        while (t.right != null) {
            t = t.right;
        }
        t.right = tmpRight;
    }
    flatten(root.right);
}

Reverse Linked List

To reverse the whole list: use 3 pointers.

public ListNode reverse(ListNode head) {
    ListNode a = null;
    ListNode b = head;

    while (b != null) {
        ListNode c = b.next;
        b.next = a;
        a = b;
        b = c;
    }
    return a;
}

To reverse partial list from position m to n: find the node at m - 1, then reverse the requested section using 3 pointers.

public ListNode reverseBetween(ListNode head, int m , int n) {
    // write your code
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    head = dummy;


    for (int i = 0; i < m - 1; i++) {
        head = head.next;
    }
    ListNode node = head.next;
    for (int i = 0; i < n - m; i++) {
        ListNode tmp = head.next;
        head.next = node.next;
        node.next = head.next.next;
        head.next.next = tmp;
    }

    return dummy.next;
}

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            } else {
                return false;
            }
            if (fast == slow) {
                return true;
            }
        }

        return false;
    }

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

public ListNode detectCycle(ListNode head) {
    ListNode fast = head, slow = head;
    int cnt = 0;
    while(fast.next != null) {
        slow = slow.next;
        fast = fast.next;
        if (fast.next == null) return null;
        fast = fast.next;

        if (slow == fast) {
            slow = head;
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
    }
    return null;
}

Palindrome Linked List

LeetCode 234 Solution

Given a singly linked list, determine if it is a palindrome.

Follow up: Could you do it in O(n) time and O(1) space?

Solution 1: Reverse and compare

Reverse the linked list, if it is a palindrome, the reversed linked list should be the same as the original one. Actually we can just compare half of the list.

Solution 2: Use Stack

Push half of the list to a stack and compare the popped nodes from the stack to the rest of the list.

public boolean isPalindrome(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;

    Stack<Integer> stack = new Stack<>();

    while (fast != null && fast.next != null) {
        stack.push(slow.val);
        slow = slow.next;
        fast = fast.next.next;
    }

    if (fast != null) {
        slow = slow.next;
    }

    while (slow != null) {
        if (slow.val != stack.pop()) return false;
        slow = slow.next;
    }

    return true;
}

Solution 3: Recursive

  • if the length is 0 or 1, the list is a palindrome
  • if the first and the last node are removed, the remaining list is a palindrome, and the first and the last node have the same value, then the full list is a palindrome.

illustration:

(0 (1 (2 (3) 2) 1) 0)

Code:

public boolean isPalindrome(ListNode head) {
    int len = 0;
    ListNode tmp = head;
    while (tmp != null) {
        tmp = tmp.next;
        len++;
    }

    return recursive(head, len).result;
}

private Result recursive(ListNode head, int length) {
    if (head == null || length == 0) {
        return new Result(null, true);
    } else if (length == 1) {
        return new Result(head.next, true);
    } else if (length == 2) {
        return new Result(head.next.next, head.val == head.next.val);
    }

    Result res = recursive(head.next, length - 2);

    if (!res.result || res.node == null) {
        return res;
    } else {
        res.result = (head.val == res.node.val);
        res.node = res.node.next;
        return res;
    }
}

class Result {
    ListNode node;
    boolean result;
    public Result(ListNode node, boolean result) {
        this.node = node;
        this.result = result;
    }
}

Remove Duplicates From Sorted List

Problem 1

Delete all duplicates such that each element appear only once.

public static ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = head;
    while (head != null) {
        while (head.next != null && head.next.val == head.val) {
            head.next = head.next.next;
        }
        head = head.next;
    }
    return dummy;
}

Problem 2

Delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

public ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode p = dummy;
    while (p.next != null) {
        if (p.next.next != null && p.next.val == p.next.next.val) {
            int val = p.next.val;
            while (p.next != null && p.next.val == val) {
                p.next = p.next.next;
            }
        } else {
            p = p.next;
        }

    }
    return dummy.next;
}