Top 10 Linked List Coding Problems (with Solutions)
1. Reverse a Linked List
Reverse a singly linked list.
Code:
ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
2. Detect a Cycle in Linked List
Check if a cycle exists in a linked list using Floyd's algorithm.
Code:
boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
3. Find the Middle of a Linked List
Return the middle node of a linked list.
Code:
ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
4. Merge Two Sorted Linked Lists
Merge two sorted linked lists.
Code:
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
5. Remove Nth Node from End
Remove the nth node from the end of a linked list.
Code:
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
for (int i = 0; i <= n; i++) fast = fast.next;
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
6. Add Two Numbers Represented by Linked Lists
Add two linked lists where each node contains a single digit.
Code:
ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), curr = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) { sum += l1.val; l1 = l1.next; }
if (l2 != null) { sum += l2.val; l2 = l2.next; }
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
}
return dummy.next;
}
7. Intersection of Two Linked Lists
Find the node at which two linked lists intersect.
Code:
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
a = (a == null) ? headB : a.next;
b = (b == null) ? headA : b.next;
}
return a;
}
8. Remove Duplicates from Sorted List
Remove duplicates from a sorted linked list.
Code:
ListNode deleteDuplicates(ListNode head) {
ListNode curr = head;
while (curr != null && curr.next != null) {
if (curr.val == curr.next.val)
curr.next = curr.next.next;
else
curr = curr.next;
}
return head;
}
9. Rotate Linked List
Rotate the list to the right by k places.
Code:
ListNode rotateRight(ListNode head, int k) {
if (head == null) return null;
int len = 1;
ListNode tail = head;
while (tail.next != null) { tail = tail.next; len++; }
k %= len;
if (k == 0) return head;
tail.next = head;
for (int i = 0; i < len - k; i++) tail = tail.next;
ListNode newHead = tail.next;
tail.next = null;
return newHead;
}
10. Flatten a Linked List with Child Pointers
Flatten a multi-level linked list into a single-level list.
This often requires recursion or a stack.
(Code not shown for brevity)
