Linked List Flashcards
- Add Two Numbers
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.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
Use two pointers. One pointer for each list.
Use dummy node is better.
while l1 or l2 or carrier
Keep maintain the sum and carry.
After both lists are empty. if still has a carrier, add a new node.
- Remove Nth Node From End of List
Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Follow up:
Could you do this in one pass?
Use two pointer. Fast, slow. Fast is n+1 step faster than slow. Once the fast pointer meet the end. The slow pointer just bypass the next pointer. slow.next=slow.next.next
Use two loop. First loop let hte fast is n+1 step faster than slow. Second loop, both pointer go together. Stop when fast pointer meet the end.
- Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Use two-pointer. One on l1. one on l2. Let the smaller first node as l1. Then compare two-pointer p1,p2. If p2 > p1.next: p1=p1.next else: insert the p2. and let p2 go one step. p1 go one step.
Or use recursive is more concise(return a or b will return the first one).
class Solution:
def mergeTwoLists(self, a, b):
if a and b:
if a.val > b.val:
a, b = b, a
a.next = self.mergeTwoLists(a.next, b)
return a or b
- Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
Use a list of pointers. And use a priority queue to save(node.val, node) track the smallest element and add the smallest list.
OR
Use DIvide and conquer. The naive thought is to merge two list k-1 times. But if using Divide and conquer, you can merge logk time.
- Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list’s nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
Use a dummy node. Start from the dummy node.
if cur.next and cur.next.next: then swap the next to nodes.
Then cur = cur.next.next
- Rotate List
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
Use two pointer. fast and slow. fast is k step faster than slow.
Two loops. First loop let fast pointer go k step.
second loop, both pointer go together untill the fast reach the end
while(fast.next)
Then fast.next = slow
dummy.next = slow.next
slow.next = None
Note: if k»_space; len(lsit). It will be very slow. So we should calculate the length first. Then let k=k % len(list).
These processes above can be done with one pointer too. Just do the fast pointer job first then slow pointer later.
- Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Return the linked list sorted as well.
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 2->3
Two pointers. fast and slow. If next node and next.next node is the different value. Then both pointers go one step. If they are the same. Then let the fast pointer keep going until met the different value. Then slow.next = fast
- Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2
Output: 1->2
Example 2:
Input: 1->1->2->3->3
Output: 1->2->3
Use one pointer. If cur.next.val == cur.val. Then cur.next = cur.next.next just skip it.
- Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
maintain two list. l1, l2. If the valuse is lower then x. go to l1. otherwise go to l2. Then concat l1,l2 together,
- Reverse Linked List II
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
The first loop goes m steps. And remember prev as m-1 node.
link cur to next.next, next to first of reverse, pre to next.
while(n-m):
next = cur.next
cur.next = next.next
next.next = pre.next
pre.next = next
n -= 1- Reverse Linked List
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
prev, cur = None, head
while(cur):
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
return prev
class Solution:
# @param {ListNode} head
# @return {ListNode}
def reverseList(self, head):
return self._reverse(head)
def _reverse(self, cur, prev=None):
if not cur:
return prev
tmp= cur.next
cur.next = prev
return self._reverse(tmp, node)
- Copy List with Random Pointer
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.
The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
Example 4:
Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.
Constraints:
-10000 <= Node.val <= 10000
Node.random is null or pointing to a node in the linked list.
Number of Nodes will not exceed 1000.
walk through the whole list. And copy the node.val to a new list. Meanwhile, use a hashmap to save the map of node and new node.
table = {None:None}
table[node]=copy_node.
loop the new list and old list.
copy_node.random = table[node.random]- Linked List Cycle
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
Use two pointer. Fast slow pointer. Fast always go two steps. slow always go one step.
public boolean hasCycle(ListNode head) {
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;
}- Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
Follow-up:
Can you solve it without using extra space?
- Use hashmap to memorize the node you have walked before. once met the node again, it is the begin of cycle.
- 這是要用算出來的
主要做法就是fast, slow先一起走，直到遇到。遇到之後，head和slow一起走，遇到的地方就是起點。
a head to first node of cycle
b first node of cycle to the node fast and slow met
c the node fast and slow met to the end of cycle
從head走到cycle中間的點並且遇到a+b
同時fast也走了a+b+nL = 2(a+b)
所以 a+b = nL => nL - b = a -> (n-1)L + c = a
- Reorder List
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list’s nodes, only nodes itself may be changed.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
find the middle of the list.
Partition the list into two list.
Then reverse the second list.
Then loop the two list and merge together.
