Linked List in Java

Cheatsheet Content

1. Introduction to Linked Lists Definition: A linear data structure where elements are not stored at contiguous memory locations. Each element (node) points to the next. Components of a Node: Data: The value stored in the node. Next Pointer: A reference to the next node in the sequence. Advantages: Dynamic size, ease of insertion/deletion. Disadvantages: Random access is not allowed (no direct indexing), extra memory for pointers. 2. Types of Linked Lists Singly Linked List: Each node points to the next node. class Node { int data; Node next; Node(int d) { data = d; next = null; } } Doubly Linked List: Each node has pointers to both the next and previous nodes. class DNode { int data; DNode next; DNode prev; DNode(int d) { data = d; next = null; prev = null; } } Circular Linked List: The last node points back to the first node, forming a circle. Can be singly or doubly circular. 3. Common Operations (Singly Linked List) 3.1. Insertion At the Beginning: void insertAtHead(int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; } At the End: void insertAtEnd(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; return; } Node current = head; while (current.next != null) { current = current.next; } current.next = newNode; } After a Given Node: void insertAfter(Node prevNode, int data) { if (prevNode == null) return; Node newNode = new Node(data); newNode.next = prevNode.next; prevNode.next = newNode; } 3.2. Deletion By Key: void deleteNode(int key) { Node temp = head, prev = null; if (temp != null && temp.data == key) { head = temp.next; return; } while (temp != null && temp.data != key) { prev = temp; temp = temp.next; } if (temp == null) return; // Key not found prev.next = temp.next; } At a Given Position: void deleteNodeAtPos(int position) { if (head == null) return; if (position == 0) { head = head.next; return; } Node current = head; for (int i = 0; current != null && i 3.3. Traversal and Search Traversal: void printList() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } Search: boolean search(int key) { Node current = head; while (current != null) { if (current.data == key) return true; current = current.next; } return false; } 4. Important LeetCode Questions 206. Reverse Linked List: Reverse a singly linked list. Techniques: Iterative (three pointers: $prev, curr, nextTemp$), Recursive. 21. Merge Two Sorted Lists: Merge two sorted linked lists into one new sorted list. Techniques: Iterative, Recursive. 141. Linked List Cycle: Determine if a linked list has a cycle. Techniques: Floyd's Cycle-Finding Algorithm (Fast and Slow Pointers). 142. Linked List Cycle II: Find the node where a cycle begins. Techniques: Fast and Slow Pointers (after finding a cycle, move one pointer to head and both at same pace). 19. Remove Nth Node From End of List: Remove the $n$-th node from the end of a linked list and return its head. Techniques: Two-pointer approach (fast and slow, $n$ distance apart). 234. Palindrome Linked List: Check if a singly linked list is a palindrome. Techniques: Find middle, reverse second half, compare. 876. Middle of the Linked List: Find the middle node of a singly linked list. Techniques: Fast and Slow Pointers. 2. Add Two Numbers: Add two numbers represented by linked lists (digits in reverse order). Techniques: Iterative traversal, handling carry. 138. Copy List with Random Pointer: Copy a linked list where each node has a `next` and a `random` pointer. Techniques: Hashing, or weaving new nodes into existing list. 23. Merge k Sorted Lists: Merge $k$ sorted linked lists into one sorted linked list. Techniques: Divide and Conquer, Min-Heap (Priority Queue).