Delete Node in a Linked List
★☆☆☆☆
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
Reverse Linked List
☆☆☆☆☆
public class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
while (head != null) {
ListNode nxt = head.next;
head.next = pre;
pre = head;
head = nxt;
}
return pre;
}
}
Odd Even Linked List
★★★☆☆
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example: Given
1->2->3->4->5->NULL, return1->3->5->2->4->NULLNote: The relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on ...
Note: harder than you think! might easily get too complicate and fail Note: key is to connect two nodes at a time, think of who might become null and will you call null's next?
public ListNode oddEvenList(ListNode head) {
if (head == null) return null;
ListNode odd = head, even = head.next, ehead = head.next;
while (even != null && even.next != null) {
odd.next = even.next;
even.next = odd.next.next;
odd = odd.next;
even = even.next;
}
odd.next = ehead;
return head;
}
Intersection of Two Linked Lists
★★★☆☆
Write a program to find the node at which the intersection of two singly linked lists begins.
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3ans: c1
Notes:
- if headA and headB has intersection, L1+L2
must have same tailas L2+L1, checking L1 + L2 is enough- even if no intersection, using while (L1 != L2) will terminate when
L1 == L2 == nulland return null- at the end, should
return L1orreturn L2instead ofreturn null, try cases like [3] and [2, 3]
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode L1 = headA;
ListNode L2 = headB;
while (L1 != L2) {
L1 = L1.next;
L2 = L2.next;
if (L1 == L2) return L1;
if (L1 == null) L1 = headB;
if (L2 == null) L2 = headA;
}
return L1;
}
Merge Two Sorted Lists
★★☆☆☆
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Iterative solution is easy to get wrong
- using while (l1 != null || l1 != null) would be more complicated to handle, since you need to make sure
newtail.next = nullin the end.- if you use while (l1 != null && l2 != null) => there must be one list end first, and you can connect the other's head to the tail,
newtail.next = nullwould become trivial.
// recursive
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l2.next, l1);
return l2;
}
}
// iterative
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode newhead = null;
if (l1.val < l2.val) {
newhead = l1;
l1 = l1.next;
}
else {
newhead = l2;
l2 = l2.next;
}
ListNode newtail = newhead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
newtail.next = l1;
l1 = l1.next;
newtail = newtail.next;
}
else {
newtail.next = l2;
l2 = l2.next;
newtail = newtail.next;
}
}
if (l1 == null) newtail.next = l2;
if (l2 == null) newtail.next = l1;
return newhead;
}
Merge k Sorted Lists
★★☆☆☆
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
//divide and conquer solution
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
if (lists.length == 1) return lists[0];
if (lists.length == 2) return merge2Lists(lists[0], lists[1]);
int mid = lists.length / 2 ;
ListNode a = mergeKLists(Arrays.copyOfRange(lists, 0, mid + 1));
ListNode b = mergeKLists(Arrays.copyOfRange(lists, mid + 1, lists.length));
return merge2Lists(a, b);
}
public ListNode merge2Lists(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0);
ListNode ptr = dummy;
while (a != null && b != null) {
if (a.val <= b.val) {
ptr.next = a;
a = a.next;
}
else {
ptr.next = b;
b = b.next;
}
ptr = ptr.next;
}
if (a == null) ptr.next = b;
if (b == null) ptr.next = a;
return dummy.next;
}
Palindrome Linked List
★★★☆☆
Given a singly linked list, determine if it is a palindrome. Do it in O(n) time and O(1) space?
Note:
- Find middle first (as well as reversed the previous part), then compare left part and right part!
- Use ' to help you recognize the node after updating!
Symbols N: null, p: prev, n: nxt, s: slow, f: fast, <-: done with reverse connect even case, after termination N 1 2 2 1 p <-s f f' p' n s' odd case, after termination N 1 2 3 N p <-s f f' p' n s'
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head, fast = head.next, prev = null, nxt = null;
while (fast != null && fast.next != null) {
fast = fast.next.next;
nxt = slow.next;
slow.next = prev;
prev = slow;
slow = nxt;
}
ListNode leftHead = null, rightHead = null;
if (fast != null) {
leftHead = slow;
rightHead = slow.next;
slow.next = prev;
}
else {
leftHead = prev;
rightHead = slow.next;
}
while (rightHead != null) {
if (rightHead.val != leftHead.val) return false;
rightHead = rightHead.next;
leftHead = leftHead.next;
}
return true;
}