LinkedList
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curt = head;
while (curt != null) {
ListNode next = curt.next;
curt.next = prev;
prev = curt;
curt = next;
}
return prev;
}Recursion
ListNode newhead = null;
public ListNode reverseList(ListNode head) {
if (head == null) return null;
helper(head);
return newhead;
}
private ListNode helper(ListNode curt) {
if (curt.next == null) {
newhead = curt;
return curt;
}
ListNode next = helper(curt.next);
curt.next.next = curt;
curt.next = null;
return next;
}Use a curt pointer and a nxt pointer to move from head. Detect if curt.val == nxt.val then remove nxt node.
def deleteDuplicates(self, head: ListNode) -> ListNode:
curt = head
while curt is not None:
nxt = curt.next
if nxt and nxt.val == curt.val:
curt.next = nxt.next
else:
curt = curt.next
return headUse dummy node, and a current node starts at dummy. While the first and second list is not null, add the smaller node and move forward.
When end, detect the unfinished list, add to the end.
Iteration T: O(n + m) S: O(1)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curt = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
curt.next = l1;
l1 = l1.next;
} else {
curt.next = l2;
l2 = l2.next;
}
curt = curt.next;
}
if (l1 == null) {
curt.next = l2;
}
if (l2 == null) {
curt.next = l1;
}
return dummy.next;
}Recursion T: O(n + m) S: O(m + n)
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 == None and l2 == None:
return None
if l1 != None and l2 == None:
return l1
if l1 == None and l2 != None:
return l2
if l1.val <= l2.val :
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else :
l2.next = self.mergeTwoLists(l1, l2.next)
return l2Divide and Conquer, Merge sort T: O(n*logk) S: O(1)
public ListNode mergeKLists(ListNode[] lists) {
return helper(lists, 0, lists.length - 1);
}
private ListNode helper(ListNode[] lists, int start, int end) {
if (start == end) return lists[start];
else if (start > end) {
return null;
} else {
int mid = start + (end - start) / 2;
return mergeTwo(helper(lists, start, mid), helper(lists, mid + 1, end));
}
}
private ListNode mergeTwo(ListNode A, ListNode B) {
if (A == null) return B;
if (B == null) return A;
if (A.val < B.val) {
A.next = mergeTwo(A.next, B);
return A;
} else {
B.next = mergeTwo(A, B.next);
return B;
}
}2. PQ T: O(nlogk) S: O(n)
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((l1, l2) -> Integer.compare(l1.val, l2.val));
for (ListNode list : lists) {
if (list == null) {
continue;
}
pq.offer(list);
}
ListNode dummy = new ListNode(-1);
ListNode iterator = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
iterator.next = node;
iterator = node;
if (node.next != null) {
pq.offer(node.next);
}
}
return dummy.next;
}Construct node and take carry.
T: O(max(m, n)) S: O(max(m, n))
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
int carry = 0;
ListNode node = dummy;
while (l1 != null || l2 != null || carry != 0) {
int v1 = l1 == null ? 0 : l1.val;
int v2 = l2 == null ? 0 : l2.val;
int sum = v1 + v2 + carry;
carry = sum / 10;
node.next = new ListNode(sum % 10);
node = node.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}Use two stacks to store two lists separately. Pop node and construct new node, insert between dummy and dummy.next.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
while (l1 != null) {
s1.add(l1.val);
l1 = l1.next;
}
while (l2 != null) {
s2.add(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode dummy = new ListNode(0);
while (!s1.isEmpty() || !s2.isEmpty()) {
int one = s1.isEmpty() ? 0 : s1.pop();
int two = s2.isEmpty() ? 0 : s2.pop();
int sum = one + two + carry;
ListNode curt = new ListNode(sum % 10);
carry = sum / 10;
curt.next = dummy.next;
dummy.next = curt;
}
if (carry == 1) dummy.val = 1;
return dummy.val == 1 ? dummy : dummy.next;
} def hasCycle(self, head: ListNode) -> bool:
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False def detectCycle(self, head: ListNode) -> ListNode:
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return fast
return None def swapPairs(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
dummy = ListNode(-1)
dummy.next = head
pre = dummy
curt = head
while curt is not None and curt.next is not None:
nxt = curt.next
curt.next = nxt.next
nxt.next = pre.next
pre.next = nxt
pre = curt
curt = pre.next
return dummy.next def oddEvenList(self, head: ListNode) -> ListNode:
if not head:
return None
even = head
odd = head.next
oddhead = odd
while odd and odd.next:
even.next = odd.next
even = even.next
odd.next = even.next
odd = odd.next
even.next = oddhead
return head
记录一个pre，把pre移动到开始reverse的前面
pre不动，把后面的reverse，把next接在pre和pre.next 中间
Return dummy.next
T: O(n) S: O(1) in-place
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
for (int i = 0; i < m - 1; i++) {
pre = pre.next;
}
ListNode curt = pre.next;
for (int i = 0; i < n - m; i++) {
ListNode next = curt.next;
curt.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummy.next;
}19. Remove Nth Node From End of List
一个fast, 一个slow 都从dummy 走
Fast走 i = 0 ： n。这样fast和尾的距离是total - n，
slow，fast同时走，fast是null的时候，slow走了total -n ，slow和尾的距离是n
删除slow后面节点
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(-1)
dummy.next = head
fast = dummy
slow = dummy
i = 0
while i <= n and fast:
fast = fast.next
i += 1
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next83. Remove Duplicates from Sorted List
一个指针，如果curt.val == curt.next.val 情况下curt.next = curt.next.next
def deleteDuplicates(self, head: ListNode) -> ListNode:
curt = head
while curt is not None:
nxt = curt.next
if nxt and nxt.val == curt.val:
curt.next = nxt.next
else:
curt = curt.next
return head82. Remove Duplicates from Sorted List II
两个指针走，在curt.next.val == curt.val情况下移动curt
如果pre的下一个不是curt，说明有duplicate，
否则同时移动pre和curt
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = ListNode(-1)
dummy.next = head
pre = dummy
curt = head
while curt is not None:
while curt.next is not None and curt.val == curt.next.val :
curt = curt.next
if pre.next is not curt:
pre.next = curt.next
curt = pre.next
else :
pre = pre.next
curt = pre.next
return dummy.next203. Remove Linked List Elements
Curt从dummy走，在curt.next.val == val的情况下，curt.next = curt.next.next
def removeElements(self, head: ListNode, val: int) -> ListNode:
if head is None:
return None
dummy = ListNode(-1)
dummy.next = head
pre = dummy
curt = head
while curt is not None:
if curt.val == val:
curt = curt.next
pre.next = curt
else :
pre = pre.next
curt = curt.next
return dummy.next这个题要说把linkedlist最后一个节点+1。如果有进位的话加到前面那个node。这样对于单向列表很麻烦，用recursion做非常直观。
如果碰到null，return 1，因为最后一位+1；
加上carry之后如果大于9，reassign value.返回1
否则返回0
这样的话有可能多出来一个node，用dummy来处理
160. Intersection of Two Linked Lists
先把两个list的长度求出来，减少长的那个，这样如果他们相等，就代表他们到最后的距离是相等的。这样说明两个head继续走，走到他们相等的时候就return。否则return null.
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = getLen(headA);
int lenB = getLen(headB);
while (lenA > lenB) {
headA = headA.next;
lenA--;
}
while (lenA < lenB) {
headB = headB.next;
lenB--;
}
while (headA != null || headB != null) {
if (headA == headB) return headA;
headA = headA.next;
headB = headB.next;
}
return null;
}
private int getLen(ListNode head) {
int count = 0;
while (head != null) {
head = head.next;
count++;
}
return count;
}Same method as 141, 142.
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode dummyA = headA;
ListNode dummyB = headB;
while (headA != headB) {
headA = headA == null ? dummyB : headA.next;
headB = headB == null ? dummyA : headB.next;
}
return headA;
}Use a Hash-map to store original and it is corresponding new node. Loop over it and set the random pointer.
public Node copyRandomList(Node head) {
Node dummy = new Node(-1);
Node pre = dummy;
Node curt = head;
Map<Node, Node> map = new HashMap<>();
while (curt != null) {
map.putIfAbsent(curt, new Node(curt.val));
pre.next = map.get(curt);
curt = curt.next;
pre = pre.next;
}
curt = head;
while (curt != null) {
map.get(curt).random = map.get(curt.random);
curt = curt.next;
}
return dummy.next;
}Add the new node next to the original node. For example 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
public Node copyRandomList(Node head) {
Node dummy = new Node(-1);
Node curt = head;
while (curt != null) {
Node sec = curt.next;
curt.next = new Node(curt.val);
curt.next.next = sec;
curt = sec;
}
curt = head;
Node pre = dummy;
while (curt != null) {
if (curt.random != null) curt.next.random = curt.random.next;
curt = curt.next.next;
}
curt = head;
while (curt != null) {
Node nxt = curt.next;
curt.next = nxt.next;
pre.next = nxt;
pre = pre.next;
curt = curt.next;
}
return dummy.next;
}Palindrome特性是从中间到两边对称。一般Palindrome都涉及到单双数的问题。这个题也是找中点，然后从中点往两边比较是不是Palindrome。
找中点用快慢指针, while (fast.next != null && fast.next.next != null)
Fast到头之后，check一下fast是不是null，如果不是，说明是even，slow还要往前走一个。
这样从slow到尾reverse()。用reverse LinkedList变成这样：
最后从head和slow 走，看看是不是相等
def isPalindrome(self, head: ListNode) -> bool:
if not head or not head.next:
return True
fast = head
pre = head
slow = head
while fast and fast.next:
fast = fast.next.next
pre = slow
slow = slow.next
if fast:
pre = pre.next
curt = pre.next
while curt and curt.next:
nxt = curt.next
curt.next = nxt.next
nxt.next = pre.next
pre.next = nxt
fast = head
slow = pre.next
while slow and fast:
if fast.val != slow.val:
return False
fast = fast.next
slow = slow.next
return True def partition(self, head: ListNode, x: int) -> ListNode:
largehead = ListNode(-1)
largecurt = largehead
dummy = ListNode(-1)
dummy.next = head
pre = dummy
curt = head
while curt:
if curt.val >= x:
pre.next = curt.next
curt.next = largecurt.next
largecurt.next = curt
largecurt = curt
curt = pre.next
else:
pre = pre.next
curt = curt.next
pre.next = largehead.next
return dummy.next从 1->2->3->4, reorder it to 1->4->2->3。这样可以把list分成左右两段，反转后面的，然后相互插入形成结果。
快慢指针找中点，把slow记录一下成为preMiddle，然后slow = slow.next;
这样preMiddle后面的，也就是从slow开始，都要reverse。就是把slow.next都插入到preMiddle.next。
然后再互相merge
def reorderList(self, head: ListNode) -> None:
if not head or not head.next:
return
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
curt = slow.next
while curt and curt.next:
nxt = curt.next
curt.next = nxt.next
nxt.next = slow.next
slow.next = nxt
fast = slow.next
slow.next = None
slow = head
while fast and slow:
fn = fast.next
fast.next = slow.next
slow.next = fast
slow = fast.next
fast = fn这题一看就是merge sort。跟传统merge sort一样，不过最后要merge两个list。还是先快慢指针分一半。用一个pre记录slow之前的点，然后把pre.next = null;这样recursively两边再分，最后merge。 Merge时候注意null pointer
这个题是说把后面数k个Node接到前面去，有个情况就是k会比总长度大。k % length == 0 说明不用rotate。这种情况用k % length就会得到从前往后要多少个接到前面， length - k % length是从后往前有多少接到前面。
先一个指针找长度，另外一个指针走length - k % length，把两个指针中间接到前面去。（两个指针都从dummy 走）
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head or not head.next or k == 0:
return head
dummy = ListNode(-1)
dummy.next = head
length = self.getLen(head)
pre = dummy
if k % length == 0:
return dummy.next
for i in range(length - k % length):
pre = pre.next
curt = pre.next
pre.next = None
dummy.next = curt
while curt and curt.next:
curt = curt.next
if curt:
curt.next = head
return dummy.next
def getLen(self, head):
i = 0
curt = head
while curt:
i += 1
curt = curt.next
return i
Use a range pointer to detect if the range is out of scope. Reverse the part next to pre for k - 1 times.
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode range = pre;
while (true) {
for (int i = 0; i < k && range != null; i++) {
range = range.next;
if (range == null) return dummy.next;
}
ListNode curt = pre.next;
for (int i = 0; i < k - 1; i++) {
ListNode next = curt.next;
curt.next = next.next;
next.next = pre.next;
pre.next = next;
}
pre = curt;
range = pre;
}
}1669. Merge In Between Linked Lists
function mergeInBetween(list1: ListNode | null, a: number, b: number, list2: ListNode | null): ListNode | null {
const dummy = new ListNode(-1, list1);
// Find node before index a
let prevA = dummy;
for (let i = 0; i < a; i++) {
if (prevA.next === null) break;
prevA = prevA.next;
}
// Find node at index b
let afterB = prevA;
for (let i = a; i <= b; i++) {
if (afterB.next === null) break;
afterB = afterB.next;
}
// Connect prevA.next to list2 head
prevA.next = list2;
// Find tail of list2
let tail2 = list2;
while (tail2 !== null && tail2.next !== null) {
tail2 = tail2.next;
}
// Connect tail of list2 to node after b
if (tail2 !== null) {
tail2.next = afterB.next;
}
return dummy.next;
};
Last updated
Was this helpful?