Leetcode 2. Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Analysis:

• Initialize current node to dummy head of the returning list.
• Initialize carry to $0$.
• Initialize $p$ and $q$ to head of $l1$ and $l2$ respectively.
• Loop through lists $l1$ and $l2$ until you reach both ends.
  • Set $x$ to node $p$‘s value. If $p$ has reached the end of $l1$, set to $0$.
  • Set $y$ to node $q$‘s value. If $q$ has reached the end of $l2$, set to $0$.
  • Set $sum=x+y+carry$.
  • Update $carry=sum/10$.
  • Create a new node with the digit value of $(summod10)$ and set it to current node’s next, then advance current node to next.
  • Advance both $p$ and $q$.
• Check if $carry=1$, if so append a new node with digit $1$ to the returning list.
• Return dummy head’s next node.

Time complexity: O(max(m, n))

Space complexity: O(max(m, n))

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // O(n) O(1)
        
        if (l1 == null || l2 == null) {
            return null;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        int sum = 0;
        int carry = 0;
        
        while (l1 != null || l2 != null) {
            int num1 = l1 == null ? 0 : l1.val;
            int num2 = l2 == null ? 0 : l2.val;
            
            sum = num1 + num2 + carry;
            
            // update the next node
            cur.next = new ListNode(sum % 10);
            
            cur = cur.next;
            carry = sum / 10;
            
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        
        // Check the last corner case
        if (carry != 0) {
            cur.next = new ListNode(carry);
        }
        
        return dummy.next;
    }
}

Leetcode 160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.

• The linked lists must retain their original structure after the function returns.

• You may assume there are no cycles anywhere in the entire linked structure.

• Your code should preferably run in O(n) time and use only O(1) memory.

Analysis:

3 steps:

• Get the length of both list
• Let the longer list to go before len1-len2 steps
• Make the lists go further, if they’re the same, then we find it

Time complexity: O(m + n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // O(m + n)
        
        if (headA == null || headB == null) {
            return null;
        }
        
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        
        // Let the longer list to go before lenA - lenB 
        for (int i = 0; i < Math.abs(lenA - lenB); i++) {             if (lenA > lenB) {
                headA = headA.next;
            } else {
                headB = headB.next;
            }
        }
        
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        
        return null;
    }
    
    public int getLength(ListNode head) {
        int len = 0;
        
        while (head != null) {
            head = head.next;
            len++;
        }
        
        return len;
    }
}

Leetcode 21. 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.

Analysis:

Make a dummy node, compare the two values in the two lists. If one is smaller, add it to the head. Update the head to next.

Note: the two lists may not be the same length. After all iteration, we need to check the lefts and add them to the result.

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // O(n)
        
        if (l1 == null) {
            return l2;
        }
        
        if (l2 == null) {
            return l1;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            
            cur = cur.next;
        }
        
        // Check if there're lefts
        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }
        
        return dummy.next;
    }
}

Leetcode 25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Analysis:

We need to keep a count of the node. If the count % k == 0, then we reverse the node between this range.

/**

* Reverse a link list between pre and next exclusively

* an example:

* a linked list:

* 0->1->2->3->4->5->6

* |           |

* pre        next

* after call pre = reverse(pre, next)

*

* 0->3->2->1->4->5->6

*          |  |

*          pre next

*

* @return the reversed list’s last node, which is the precedence of parameter next

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // O(n)
        
        if (head == null || head.next == null || k < 2) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        dummy.next = head;
        
        int count = 0;
        while (head != null) {
            count++;
            if (count % k == 0) {
                prev = reverseList(prev, head.next);
                head = prev.next;
            } else {
                head = head.next;
            }
        }
        return dummy.next;
    }
    
    // reverse list node from prev to end - 1
    public ListNode reverseList(ListNode prev, ListNode end) {
        ListNode cur = prev.next;
        ListNode temp = cur.next;
        
        while (temp != end) {
            cur.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
            temp = cur.next;
        }
        
        return cur;
    }
}

Leetcode 24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Analysis:

Have a dummy node and a temporal node. Iterate the whole list and change every node pair.

Nice to have the figure to help understand.

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        // O(n)
        
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        dummy.next = head;
        
        while (head != null && head.next != null) {
            // First operation
            node.next = head.next;
            head.next = node.next.next;
            node.next.next = head;
            
            // Go to another round
            node = head;
            head = head.next;
        }
        
        return dummy.next;
    }
}

Leetcode 92 & 206. Reverse Linked List I & II

Reverse a singly linked list.

click to show more hints.

Hint:A linked list can be reversed either iteratively or recursively. Could you implement both?

Analysis:

For iteration, we need to have a prev and next node for temporal save.

For recursive,

Assume that the rest of the list had already been reversed, now how do I reverse the front part? Let’s assume the list is: n₁ → … → n_k-1 → n_k → n_k+1 → … → n_m → Ø

Assume from node n_k+1 to n_m had been reversed and you are at node n_k.

n₁ → … → n_k-1 → n_k → n_k+1 ← … ← n_m

We want n_k+1’s next node to point to n_k.

So, n_k.next.next = n_k

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        // O(n)
        
        if (head == null || head.next == null) {
            return null;
        }
        
        // iteration
        ListNode current = head;
        ListNode prev = null;
        ListNode next;
        
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        
        return prev;
        
        // recursive
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        
        return p;
    }
}

Followup:
Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Analysis:
Go through the list and find the position before m. Then start from m, reverse the n-m nodes like reverse linked list.

Time complexity: O(n)
Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // O(n)
        
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        dummy.next = head;
        
        // Find the position before the reverse start
        for (int i = 0; i < m - 1; i++) {
            prev = prev.next;
        }
        
        // Reverse the n - m nodes
        ListNode cur = prev.next;
        for (int i = 0; i < n - m; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }
        
        return dummy.next;
    }
}

Leetcode 141 & 142. Linked List Cycle I & II

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Analysis:

Typical two pointer questions. Give two pointers fast and slow, fast run 2 steps and slow run 1 step. If there’s a cycle, finally slow == fast. If no cycle, fast == null || fast.next == null.

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        // O(n)
        
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        // while (slow != fast) {
        //     if (fast == null || fast.next == null) {
        //         return false;
        //     }
            
        //     slow = slow.next;
        //     fast = fast.next.next;
        // }
        
        // return true;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                return true;
            }
        }
        
        return false;
    }
}

Followup:
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

Analysis:
Follow the figure below:

链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c，如图所示。环的长度是L。slow和fast的速度分别是qs,qf。

第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。

因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，可以得到a=c（这个结论很重要！）。

我们发现L=b+c=a+b，也就是说，从一开始到二者第一次相遇，循环的次数就等于环的长度。

我们已经得到了结论a=c，那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // O(n)
        
        if (head == null || head.next == null) {
            return null;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            
            if (fast == slow) {
                break;
            }
        }
        
        if (fast != slow) {
            return null;
        }
        
        fast = head;
        
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        
        return fast;
    }
}

Leetcode 237. 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 -> 4after calling your function.

Analysis:

Very intuitive method.

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void deleteNode(ListNode node) {
        // O(1)
        
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Leetcode Find the middle of a Linked List

Two pointers (fast/slow) is widely used for programming interviews. For example, to find the middle of a Linked List, it can be utilized.

Basically, two pointers need to be handled, one is fast and one is slow. For the slow pointer, it moves one step each time, while fast moves two. So when the fast moves to the end of the list, the slow pointer is pointing to the middle.

The code for this part is below:

    // Find the middle of the list
    private ListNode findMid (ListNode head) {
        if (head == null) {
            return null;
        }
        
        // 2 pointers: fast slow
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }

This idea is popularly used and it should be mastered.