Linked List
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
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;
}
By Language
Go
- Linked lists: https://pkg.go.dev/container/list
- Circular lists: https://pkg.go.dev/container/ring