2. Linked List
好题
Reverse Nodes in k-Group
Insert into a sorted circular linked list
Flatten a Multilevel doubly linked list
LRU Cache
Reverse Linked List
Iterative & recursive solution 都需要掌握
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next= head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
//recursive
public ListNode reverseListRecursive(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseListRecursive(head.next);
head.next.next = head;
head.next = null;
return newHead;
}Remove duplicates from sorted list II
[1,2,2,4,4,5] -> [1,5]
[1,1,2] ->[2]
[1,2,2] ->[1]
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy, cur = dummy.next;
while (cur != null && cur.next != null) {
ListNode next = cur.next;
boolean dup = false;
while (next != null && cur.val == next.val) {
dup = true;
next = next.next;
}
if (dup) {
prev.next = next;//connect prev.next to next directly
} else {
prev = cur; //move prev 1 step forward
}
cur = next;
}
return dummy.next;
}Remove Nth Node from End of List
slow, fast pointer
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
while (n-- > 0) {
fast = fast.next;
}
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}Swap Nodes in Pairs
reverse Nodes in K-Group, k = 2的情况
需要掌握both recursive and iterative approach
//recursive solution
public ListNode swapPairs(ListNode head) {
if (head == null||head.next == null) return head;
ListNode next = head.next;
head.next = swapPairs(head.next.next);
next.next = head;
return next;
}Iterative solution
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
while (head != null && head.next != null) {
//define nodes to be swapped
ListNode first = head, second = head.next;
//swap first and second
prev.next = second;
first.next = second.next;
second.next = first;
//set prev and hand pointer
prev = first;
head = first.next;
}
return dummy.next;
}Reverse Nodes in k-Group
Swap nodes in pairs的general solution
split list into 2 parts, first k nodes and rest
if list.size() < k, return original list
else: reverse first K nodes and recursively reverseKGroup for the rest of nodes
class Solution {
/*
1.split list into 2 parts, first k nodes and rest
2.if list.size() < k, return original list
3.else: reverse first K nodes and recursively reverseKGroup for the rest of nodes
*/
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
int cnt = 0;
while (cnt < k && prev.next != null) {
prev = prev.next;
cnt++;
}
if (cnt < k) {
return head;
}
ListNode newHead = prev.next;
prev.next = null;
newHead = reverseKGroup(newHead, k);
head = reverse(head);
dummy.next = head;
prev = dummy;
while (prev != null && prev.next != null) {
prev = prev.next;
}
prev.next = newHead;
return dummy.next;
}
ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}Iterative solution
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null) return head;
int n = 0;
for (ListNode i = head; i != null; i = i.next) n++;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy, cur = head;
while (n >= k) {
ListNode tail = prev;// tail is last non-null node for K group
int i = 0;
while (i++ < k) {
tail = tail.next;
}
ListNode next = tail.next;
tail.next = null;
ListNode newHead = reverse(cur);
prev.next = newHead;
while (newHead != null && newHead.next != null) {
newHead = newHead.next;
}
newHead.next = next;
prev = newHead;
cur = next;
n -= k;
}
prev.next = cur;
return dummy.next;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}Reorder List
基础题，适合拿来练手
3步走
fast, slow指针找mid
reverse seond Half
merge 2 lists
class Solution {
/*
find mid, cut into 2 lists(list1 >= list2)
reverse list2
merge list1 and list2
*/
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode second = slow.next;
slow.next = null;
ListNode newSecond = reverse(second);
//merge
fast = head;
slow = newSecond;
while (slow != null) {
ListNode fNext = fast.next;
ListNode sNext = slow.next;
fast.next = slow;
slow.next = fNext;
fast = fNext;
slow = sNext;
}
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}Insert into a sorted circular linked list
好题
首先分成两种情况，head 是否为空
如果head不为空的话，先找到max和min
然后分两种情况讨论
insertVal >= max || insertVal <= min
insertVal在min和max之间
这题要注意避免死循环的情况
/*
1. if list is empty, then create a new head and return
2. otherwise find out the max Node, then min = max.next
2.1 if (insertVal >= max.val || insertVal <= min.val) insert between min and max
2.2 otherwise find the correct place to insert
*/
class Solution {
public Node insert(Node head, int insertVal) {
Node node = new Node(insertVal);
//empty list
if (head == null) {
node.next = node;
return node;
}
Node max = head;
while (max.val <= max.next.val && max.next != head) {//不是max.next != max, 死循环
max = max.next;
}
Node min = max.next;
Node cur = min;
if (insertVal >= max.val || insertVal <= min.val) {
max.next = node;
node.next = min;
} else {
while (cur.next.val < insertVal) {
cur = cur.next;
}
Node next = cur.next;
cur.next = node;
node.next = next;
}
return head;
}
}Flatten a Multilevel doubly linked list
好题
建立一个flattenTail函数，return tail node
然后分5种情况讨论
head is empty
no child, no next
next, no child
child, no next
child and next
class Solution {
/*
1. head is empty
2. no child, no next
3. next, no child
4. child, no next
5. child and next
*/
public Node flatten(Node head) {
flattenTail(head);
return head;
}
//return tail node
private Node flattenTail(Node head) {
if (head == null) return head; //1
if (head.child == null) {
if (head.next == null) { //2
return head;
} else {
return flattenTail(head.next); //3
}
} else {
Node child = head.child;
Node next = head.next;
head.child = null;
Node childTail = flattenTail(child);
head.next = child;
child.prev = head;
if (next != null) { //5
childTail.next = next;
next.prev = childTail;
return flattenTail(next);
}
return childTail;
}
}
}LRU Cache
initial solution
doubly linked list + hashmap
key is key, value is Node
follow up, what if only single list is allowed?
single list + hashmap
key is key, value is prevNode
Doubly list + HashMap
class LRUCache {
//doubly linked list
class Node {
int key;
int val;
Node next;
Node prev;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
Map<Integer, Node> cache;
int size;
Node dummyHead, dummyTail;
public LRUCache(int capacity) {
cache = new HashMap<>(capacity);
size = capacity;
dummyHead = new Node(-1, -1);
dummyTail = new Node(-1, -1);
dummyHead.next = dummyTail;
dummyTail.prev = dummyHead;
}
//fetch from cache
//moveFront
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
Node node = cache.get(key);
moveFront(node);
return node.val;
}
//if key exsit, update the value and moveFront
//else, if cache size exceeds, then removeTail, and then insertFront
public void put(int key, int value) {
if (cache.containsKey(key)) {
Node node = cache.get(key);
node.val = value;
moveFront(node);
return;
}
while (cache.size() >= size) {
removeTail();
}
Node node = new Node(key, value);
insertFront(node);
}
//insertFront
private void insertFront(Node node) {
//insert between dummy and head
Node head = dummyHead.next;
dummyHead.next = node;
node.prev = dummyHead;
node.next = head;
head.prev = node;
//put into map
cache.put(node.key, node);
}
//moveFront
private void moveFront(Node node) {
//connect prev and next
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
//insert between dummy and head
Node head = dummyHead.next;
dummyHead.next = node;
node.prev = dummyHead;
node.next = head;
head.prev = node;
}
//removeTail
private void removeTail() {
//connect prev and tail
Node tail = dummyTail.prev;
Node prev = tail.prev;
prev.next = dummyTail;
dummyTail.prev = prev;
//remove from map
cache.remove(tail.key);
}
}
Single list + HashMap
class LRUCache {
//single linked list
class Node {
int key;
int val;
Node next;
//Node prev;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
Map<Integer, Node> cache; //keyToPrev
int size;
Node dummyHead, tail;
//Node dummyTail; no need a dummyTail for single list
public LRUCache(int capacity) {
cache = new HashMap<>(capacity);
size = capacity;
dummyHead = new Node(-1, -1);
// dummyTail = new Node(-1, -1);
tail = dummyHead;
// dummyTail.prev = dummyHead;
}
//fetch from cache
//moveToTail
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
// Node node = cache.get(key);
moveToTail(key);
return tail.val;
}
//if key exsit, update the value and moveFront
//else, if cache size exceeds, then removeTail, and then insertFront
public void put(int key, int value) {
if (cache.containsKey(key)) {
// Node node = cache.get(key);
moveToTail(key);
tail.val = value;
} else {
//first insert, then removeHead
insertTail(key, value);
while (cache.size() > size) {
removeHead();
}
}
}
//insertTail
private void insertTail(int key, int val) {
Node node = new Node(key, val);
tail.next = node;
//put into map
cache.put(key, tail);
tail = node;
}
//moveToTail
private void moveToTail(int key) {
//connect prev and next
Node prev = cache.get(key);
Node cur = prev.next;
if (tail == cur) {
return; //corner case
}
prev.next = cur.next;
tail.next = cur;
cur.next = null;
//update in the map
cache.put(prev.next.key, prev);
cache.put(key, tail);
tail = cur;
}
//removeHead
private void removeHead() {
//connect dummyHead and head.next
Node head = dummyHead.next;
Node next = head.next;
dummyHead.next = next;
//remove head from map
cache.remove(head.key);
//re-index
cache.put(next.key, dummyHead);
}
}
Last updated
Was this helpful?