Last 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;

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

### Dummy Node

``````ListNode dummy = new ListNode(0);
``````

### 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;

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

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

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

}

}
``````

## 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);
}
``````

To reverse the whole list: use 3 pointers.

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

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) {
ListNode dummy = new ListNode(0);

for (int i = 0; i < m - 1; i++) {
}
for (int i = 0; i < n - m; i++) {
}

return dummy.next;
}
``````

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) {
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) {
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) {
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
``````

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) {

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;
while (tmp != null) {
tmp = tmp.next;
len++;
}

}

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

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

if (!res.result || res.node == null) {
return res;
} else {
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) {
}
}
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);
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;
}
``````