Han Zhu's Study Notes

Given a singly linked list, determine if it is a palindrome. Follow up: Could you do it in O(n) time and O(1) space? Thought process: Use a fast and a slow pointer to iterate through the list. At the end, slow is at the middle of the list and fast is at the end. Reverse the second half of the list. Iterate through both halves in the same time and check if they match. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome ( ListNode head ) { if ( head == null ) { return true ; } ListNode mid = getMid ( head ); ListNode midReversed = reverse ( mid ); while ( midReversed != nu...

Given a linked list, reverse the nodes of a linked list  k  at a time and return its modified list. k  is a positive integer and is less than or equal to the length of the linked 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 Thought process: Iterate through the linked list. Use two pointers to reverse k nodes at a time. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 /** * Definition for singly-linked list. * public class ListNode { * ...

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. Thought process: Iterate both linked lists twice: Get the lengths of both lists. Increment the longer list by the difference between the lists lengths. Iterate both lists again until their pointers collide. Solution 1 (Length): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 4...

You are given two  non-empty  linked lists representing two non-negative integers. 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. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Input:  (2 -> 4 -> 3) + (5 -> 6 -> 4) Output:  7 -> 0 -> 8 Thought process: Use a dummy node to start making the result list. Solve this problem just like solving an addition on paper: Iterate through both lists and pad the shorter list with 0 so that their lengths are equal. Iterate through both lists again and add numbers. If at the end carry = 1, add it to the end of result list. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 /** * Definition for singly-linked list. * public class ListNod...

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. Thought process: Divide and conquer. Recursively find the middle of the list and attach left and right sub-tree. Use an instance variable as current pointer to avoid looking for middle point in every recurrence. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { private ListNode current ; public TreeNode sortedListToBST ( ListNode head ) { current = head ; int ...

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. Thought process: The problem is that, as we iterate through the list, current.random may not have been created. One solution is to iterate through the list twice and use a hashmap.  First iteration: copy nodes' values, next pointers, and map old node -> new node. Second iteration: copy random pointers. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 /** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */ public class Solution { public RandomListNode copyRandomList ( RandomListNode head ) { if ( head == null ) { return null ; ...

Merge  k  sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Thought process: Algorithm 1: Divide and conquer. Break k lists into pairs and merge a pair at a time. Algorithm 2: Use a heap. At the start, offer the first element of each list into the heap. While the heap is not empty, poll the first element from it, and offer first.next into the heap. Solution 1 (Divide and conquer): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists ( ListNode [] lists ) { if ( lists . length == 0 ) { return null ; } return mergeKLists ( lists , 0 , lists . l...

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? Thought process: The trick is: Start with two pointers as in "141. Linked List Cycle" . After fast and slow collide in the cycle, pull either one back to head, and increment both pointers by one node in each iteration. The node where they collide again is where the cycle begins. There's no need to understand how to prove this. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 /** * 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 ) { ListNode fast = head ; ...