Linked Lists in Java

Linked lists are a fundamental data structure in Java and are widely used in Leetcode problems. Understanding their properties and operations is crucial for solving problems efficiently.

---

Table of Contents

1. Linked List Basics
2. Common Linked List Operations
3. Common Leetcode Patterns
4. Time and Space Complexity
5. Related Leetcode Questions

---

Linked List Basics

• Definition: A linked list is a linear data structure where each element (called a node) contains data and a reference (or pointer) to the next node in the sequence.

• Types:

  • Singly Linked List: Each node points to the next node.
  • Doubly Linked List: Each node points to both the next and the previous node.

• Declaration:

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

• Head: The first node in the linked list.

• Tail: The last node in the linked list (points to null).

---

Common Linked List Operations

1. Traversing a Linked List

• Example:

  ListNode current = head;
  while (current != null) {
      System.out.println(current.val);
      current = current.next;
  }

• Time Complexity: O(n)

• Space Complexity: O(1)

2. Inserting a Node

• At the Head:

  ListNode newNode = new ListNode(value);
  newNode.next = head;
  head = newNode;

  • Time Complexity: O(1)
  • Space Complexity: O(1)

• At the Tail:

  ListNode newNode = new ListNode(value);
  if (head == null) {
      head = newNode;
  } else {
      ListNode current = head;
      while (current.next != null) {
          current = current.next;
      }
      current.next = newNode;
  }

  • Time Complexity: O(n)
  • Space Complexity: O(1)

3. Deleting a Node

• By Value:

  if (head == null) return;
  if (head.val == value) {
      head = head.next;
      return;
  }
  ListNode current = head;
  while (current.next != null) {
      if (current.next.val == value) {
          current.next = current.next.next;
          return;
      }
      current = current.next;
  }

  • Time Complexity: O(n)
  • Space Complexity: O(1)

4. Reversing a Linked List

• Iterative Approach:

  ListNode prev = null;
  ListNode current = head;
  while (current != null) {
      ListNode next = current.next;
      current.next = prev;
      prev = current;
      current = next;
  }
  head = prev;

  • Time Complexity: O(n)
  • Space Complexity: O(1)

• Recursive Approach:

  public ListNode reverseList(ListNode head) {
      if (head == null || head.next == null) return head;
      ListNode p = reverseList(head.next);
      head.next.next = head;
      head.next = null;
      return p;
  }

  • Time Complexity: O(n)
  • Space Complexity: O(n) (due to recursion stack)

5. Finding the Middle of a Linked List

• Two-Pointer Technique:

  ListNode slow = head, fast = head;
  while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
  }
  return slow;

  • Time Complexity: O(n)
  • Space Complexity: O(1)

---

Common Leetcode Patterns

1. Two Pointers

• Used for problems like detecting cycles, finding the middle node, etc.

• Example:

  ListNode slow = head, fast = head;
  while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) return true; // Cycle detected
  }
  return false;

• Related Questions:

  • Linked List Cycle
  • Middle of the Linked List
  • Intersection of Two Linked Lists

2. Reversing a Linked List

• Used for problems like reverse linked list, palindrome linked list, etc.

• Example:

  ListNode prev = null;
  ListNode current = head;
  while (current != null) {
      ListNode next = current.next;
      current.next = prev;
      prev = current;
      current = next;
  }
  head = prev;

• Related Questions:

  • Reverse Linked List
  • Palindrome Linked List
  • Reverse Linked List II

3. Merge Two Sorted Lists

• Used for problems like merge two sorted lists, merge k sorted lists, etc.

• Example:

  ListNode dummy = new ListNode(0);
  ListNode current = dummy;
  while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
          current.next = l1;
          l1 = l1.next;
      } else {
          current.next = l2;
          l2 = l2.next;
      }
      current = current.next;
  }
  current.next = (l1 != null) ? l1 : l2;
  return dummy.next;

• Related Questions:

  • Merge Two Sorted Lists
  • Merge k Sorted Lists

4. Detecting and Removing Cycles

• Used for problems like linked list cycle, remove cycle, etc.

• Example:

  ListNode slow = head, fast = head;
  while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) break; // Cycle detected
  }
  if (fast == null || fast.next == null) return; // No cycle
  slow = head;
  while (slow != fast) {
      slow = slow.next;
      fast = fast.next;
  }
  fast.next = null; // Remove cycle

• Related Questions:

  • Linked List Cycle II

---

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Traversal	O(n)	O(1)
Insertion at Head	O(1)	O(1)
Insertion at Tail	O(n)	O(1)
Deletion by Value	O(n)	O(1)
Reversing (Iterative)	O(n)	O(1)
Reversing (Recursive)	O(n)	O(n)
Finding Middle	O(n)	O(1)
Detecting Cycle	O(n)	O(1)

---

Related Leetcode Questions

Easy

1. Reverse Linked List
2. Merge Two Sorted Lists
3. Palindrome Linked List

Medium

1. Linked List Cycle
2. Remove Nth Node From End of List
3. Add Two Numbers

Hard

1. Merge k Sorted Lists
2. Reverse Nodes in k-Group
3. LRU Cache