The following content is based on notes taken from a study session. It has been reorganized for clarity and understanding.
- Singly Linked List
Node structure for a singly linked list:
class Node<V> {
V value;
Node next;
}
Node structure for a doubly linked list:
class Node<V> {
V value;
Node next;
Node prev;
}
Reversing singly and doubly linked lists (omitted for brevity)
Printing common elements of two sorted linked lists (omittted for brevity)
- Problem: Determine if a singly linked list is a palindrome
Time complexity O(N), space complextiy O(1) Use fast and slow pointers, then reverse part of the list
import java.util.Scanner;
class Node {
public int val;
public Node next;
Node(int val, Node next) {
this.val = val;
this.next = next;
}
Node() {
}
}
public class Index2 {
public static boolean isPalindrome3(Node head) {
if (head == null || head.next == null) {
return true;
}
Node n1 = head;
Node n2 = head;
while (n2.next != null && n2.next.next != null) {
n1 = n1.next;
n2 = n2.next.next;
}
n2 = n1.next;
n1.next = null;
Node n3 = null;
while (n2 != null) {
n3 = n2.next;
n2.next = n1;
n1 = n2;
n2 = n3;
}
n3 = n1;
n2 = head;
boolean res = true;
while (n1 != null && n2 != null) {
if (n1.val != n2.val) {
res = false;
break;
}
n1 = n1.next;
n2 = n2.next;
}
n1 = n3.next;
n3.next = null;
while (n1 != null) {
Node temp = n1.next;
n1.next = n3;
n3 = n1;
n1 = temp;
}
return res;
}
public static Node createNode(Node head) {
Node current = head;
Scanner in = new Scanner(System.in);
int num = in.nextInt();
current.val = num;
current.next = null;
num = in.nextInt();
while (num != 0) {
Node newNode = new Node(num, null);
current.next = newNode;
current = newNode;
num = in.nextInt();
}
return head;
}
public static void printNode(Node head) {
Node current = head;
while (current != null) {
System.out.println(current.val);
current = current.next;
}
}
public static void main(String[] args) {
Node node = new Node();
node = createNode(node);
boolean result = isPalindrome3(node);
System.out.println(result);
}
}
- Partition a singly linked list into three sections: smaller, equal, and larger
Time complexity O(n), space complexity O(1)
public static Node listPartition2(Node head, int pivot) {
Node smallHead = null;
Node smallTail = null;
Node equalHead = null;
Node equalTail = null;
Node largeHead = null;
Node largeTail = null;
Node next = null;
while (head != null) {
next = head.next;
head.next = null;
if (head.val < pivot) {
if (smallHead == null) {
smallHead = head;
smallTail = head;
} else {
smallTail.next = head;
smallTail = head;
}
} else if (head.val == pivot) {
if (equalHead == null) {
equalHead = head;
equalTail = head;
} else {
equalTail.next = head;
equalTail = head;
}
} else {
if (largeHead == null) {
largeHead = head;
largeTail = head;
} else {
largeTail.next = head;
largeTail = head;
}
}
head = next;
}
if (smallTail != null) {
smallTail.next = equalHead;
if (equalTail == null) {
equalTail = smallTail;
}
}
if (equalTail != null) {
equalTail.next = largeHead;
}
return smallHead != null ? smallHead : (equalHead != null ? equalHead : largeHead);
}
- Copy a linked list with random pointers
Time complexity O(N), space complexity O(1)
Using hash map:
public static Node copyListWithRand1(Node head) {
HashMap<Node, Node> map = new HashMap<>();
Node current = head;
while (current != null) {
map.put(current, new Node(current.val, null));
current = current.next;
}
current = head;
while (current != null) {
map.get(current).next = map.get(current.next);
map.get(current).rand = map.get(current.rand);
current = current.next;
}
return map.get(head);
}
Copying nodes by inserting copies between orignial nodes:
public static Node copyListWithRand2(Node head) {
if (head == null) {
return null;
}
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = new Node(current.val, null);
current.next.next = next;
current = next;
}
current = head;
Node copy = null;
while (current != null) {
next = current.next.next;
copy = current.next;
copy.rand = current.rand != null ? current.rand.next : null;
current = next;
}
Node result = head.next;
current = head;
while (current != null) {
next = current.next.next;
copy = current.next;
current.next = next;
copy.next = next != null ? next.next : null;
current = next;
}
return result;
}
- Detect cycle in a linked list and return the first node in the cycle
public static Node getLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
Node slow = head.next;
Node fast = head.next.next;
while (slow != fast) {
if (fast.next == null || fast.next.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
- Find the first intersection node of two linked lists without cycles
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node cur1 = null;
Node cur2 = null;
if (loop1 == loop2) {
cur1 = head1;
cur2 = head2;
int lengthDiff = 0;
while (cur1 != loop1) {
lengthDiff++;
cur1 = cur1.next;
}
while (cur2 != loop2) {
lengthDiff--;
cur2 = cur2.next;
}
cur1 = lengthDiff > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
lengthDiff = Math.abs(lengthDiff);
while (lengthDiff != 0) {
lengthDiff--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else {
cur1 = loop1.next;
while (cur1 != loop1) {
if (cur1 == loop2) {
return loop2;
}
cur1 = cur1.next;
}
return null;
}
}
public static Node getIntersectNode(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node loop1 = getLoopNode(head1);
Node loop2 = getLoopNode(head2);
if (loop1 == null && loop2 == null) {
return noLoop(head1, head2);
}
if (loop1 != null && loop2 != null) {
return bothLoop(head1, loop1, head2, loop2);
}
return null;
}