一、 Singly Linked List
- Design Linked List
思路：
基础题目，注意在类里设置一个head，tail和length，可有效节约时间和简化代码。
代码：
class MyLinkedList {
static class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
this.next = null;
}
}
private Node head;
private Node tail;
private int length;
/**
* Initialize your data structure here.
*/
public MyLinkedList() {
head = new Node(0);
tail = new Node(0);
head.next = tail;
tail.next = head;
length = 0;
}
/**
* Get the value of the index-th node in the linked list. If the index is invalid, return -1.
*/
public int get(int index) {
if (index > length - 1) return -1;
if (index == length - 1) return tail.next.value;
Node p = head;
while (index-- >= 0) p = p.next;
return p.value;
}
/**
* Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
*/
public void addAtHead(int val) {
Node node = new Node(val);
node.next = head.next;
head.next = node;
if (tail.next == head) tail.next = node;
length++;
}
/**
* Append a node of value val to the last element of the linked list.
*/
public void addAtTail(int val) {
Node node = new Node(val);
node.next = tail;
tail.next.next = node;
tail.next = node;
length++;
}
/**
* Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
*/
public void addAtIndex(int index, int val) {
if (index > length) return;
if (index == length) {
addAtTail(val);
return;
}
Node p = head;
while (index-- > 0) p = p.next;
Node node = new Node(val);
node.next = p.next;
p.next = node;
length++;
}
/**
* Delete the index-th node in the linked list, if the index is valid.
*/
public void deleteAtIndex(int index) {
if (index > length - 1) return;
Node p = head;
while (index-- > 0) p = p.next;
p.next = p.next.next;
if (p.next == tail) tail.next = p;
length--;
}
public void printList() {
Node p = head.next;
while (p != tail) {
System.out.print(p.value + " ");
p = p.next;
}
System.out.println();
}
}
二、 Two Pointer Technique
- Linked List Cycle
思路：
设置两个指针，一前一后即可，可使快指针一次走两步，慢指针一次走一步，若存在环，那快指针总会在某一刻追上慢指针。注意，环可能只是链表的一部分，不一定整个链表构成一个环。
代码：
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode walker = head;
ListNode runner = head;
while (runner.next != null && runner.next.next != null) {
walker = walker.next;
runner = runner.next.next;
if (walker == runner) return true;
}
return false;
}
- Linked List Cycle II
思路1：
先说一种比较简单的思路，可以用一个Map存储对象的地址，找到第一个被重复存储的对象即可。
代码：
public ListNode detectCycle(ListNode head) {
if (head == null) return null;
HashMap<Integer, ListNode> map = new HashMap<>();
while (head != null) {
if (map.containsKey(head.hashCode())) {
return map.get(head.hashCode());
} else {
map.put(head.hashCode(), head);
}
head = head.next;
}
return null;
}
思路2：
使用双指针，还是一快一慢，快指针每次走两步，慢指针每次走一步。下图中，链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。因为快指针的速度是慢指针的两倍，所以当它们在Z点相遇时，快指针走过的路程为a+b+c+b，慢指针走过的路程为a+b，而2*(a+b)=a+b+c+b，解得a=c，故此时再令fast=head，然后fast变为每次走一步，slow还是每次走一步，当它们再相遇时就一定会在Y处。
代码：
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
while (head != slow) {
head = head.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
- Intersection of Two Linked Lists
思路：
常规思路是迭代求出两个链表的长度，然后对齐链表，找到交点即可。一种比较新颖的思路是，两个链表分别迭代，迭代到尾部时，交换链表头，这样就自动抹平了长度差异，具体见代码。
代码：
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//boundary check
if(headA == null || headB == null) return null;
ListNode a = headA;
ListNode b = headB;
//if a & b have different len, then we will stop the loop after second iteration
while( a != b){
//for the end of first iteration, we just reset the pointer to the head of another linkedlist
a = a == null? headB : a.next;
b = b == null? headA : b.next;
}
return a;
}
- Remove Nth Node From End of List
思路：
使用双指针解决，若要删除的是倒数第k个元素，则让快指针比慢指针先走k步，然后两个指针一起走，当快指针走到尾部时，慢指针就走到了倒数第k个元素。
代码：
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode front = head, back = head;
while (n-- > 0) front = front.next;
if (front == null) return head.next;
while (front.next != null) {
front = front.next;
back = back.next;
}
back.next = back.next.next;
return head;
}
三、 Classic Problems
- Reverse Linked List
思路：
比较简单，依次把每个元素插入到头指针之后即可。
代码：
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
ListNode p = head.next;
head.next = null;
while (p != null) {
ListNode pre = p;
p = p.next;
pre.next = head;
head = pre;
}
return head;
}
- Remove Linked List Elements
思路：
比较简单，注意前面加一个哨兵头指针处理起来会比较方便。
代码：
public ListNode removeElements(ListNode head, int val) {
if (head == null || (head.val == val && head.next == null)) return null;
ListNode pre = head, p = head.next;
while (p != null) {
if (p.val == val) {
pre.next = p.next;
} else {
pre = p;
}
p = p.next;
}
return head;
}
- Odd Even Linked List
思路：
比较简单，不赘述。
代码：
public ListNode oddEvenList(ListNode head) {
if (head == null) return null;
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = odd.next.next;
even.next = even.next.next;
odd = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
- Palindrome Linked List
思路：
这道题目还是比较有意思的，综合应用了前面的技巧。首先，使用快慢指针，使得慢指针停留在序列中间，然后使用链表反转慢指针到结尾的部分，然后比较这两部分是否相等即可。
代码：
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) { // odd nodes: let right half smaller
slow = slow.next;
}
slow = reverse(slow);
fast = head;
while (slow != null) {
if (fast.val != slow.val) {
return false;
}
fast = fast.next;
slow = slow.next;
}
return true;
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
四、 Conclusion
- Merge Two Sorted Lists
思路：
比较简单，不赘述
代码：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(-1);
ListNode p = head;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
while (l1 != null) {
p.next = l1;
l1 = l1.next;
p = p.next;
}
while (l2 != null) {
p.next = l2;
l2 = l2.next;
p = p.next;
}
return head.next;
}
- Add Two Numbers
思路：
比较简单，不赘述。
代码：
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = l1;
int carry = 0;
int sum = 0;
while (l1.next != null && l2.next != null) {
sum = l1.val + l2.val + carry;
l1.val = sum % 10;
carry = sum / 10;
l1 = l1.next;
l2 = l2.next;
}
if (l1.next == null) {
l1.next = l2.next;
}
sum = l1.val + l2.val + carry;
l1.val = sum % 10;
carry = sum / 10;
ListNode p = l1;
l1 = l1.next;
while (l1 != null) {
sum = l1.val + carry;
l1.val = sum % 10;
carry = sum / 10;
l1 = l1.next;
p = p.next;
}
if (carry == 1) {
p.next = new ListNode(carry);
}
return head;
}
- Flatten a Multilevel Doubly Linked List
思路：
很显然用递归解决会比较省力气，当检测到当前Node有child时，就递归进入下一层双向链表，返回值是最后一个链表元素，然后把他们串起来即可。
代码：
public Node flatten(Node head) {
if (head != null) {
Node p = recursive(head);
}
return head;
}
private Node recursive(Node head) {
Node cur = head;
while (cur.next != null) {
if (cur.child != null) {
Node p = recursive(cur.child);
p.next = cur.next;
cur.next.prev = p;
cur.child.prev = cur;
cur.next = cur.child;
cur.child = null;
}
cur = cur.next;
}
if (cur.child != null) {
Node p = recursive(cur.child);
cur.next = cur.child;
cur.child.prev = cur;
cur.child = null;
}
return cur;
}
- Copy List with Random Pointer
思路：
这道链表的深度拷贝题的难点就在于如何处理随机指针的问题，由于每一个节点都有一个随机指针，这个指针可以为空，也可以指向链表的任意一个节点，如果我们在每生成一个新节点给其随机指针赋值时，都要去遍历原链表的话，OJ上肯定会超时，所以我们可以考虑用Hash map来缩短查找时间，第一遍遍历生成所有新节点时同时建立一个原节点和新节点的哈希表，第二遍给随机指针赋值时，查找时间是常数级。
代码：
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) return null;
HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode node = head;
while (node != null) {
map.put(node, new RandomListNode(node.label));
node = node.next;
}
node = head;
while (node != null) {
map.get(node).next = map.get(node.next);
map.get(node).random = map.get(node.random);
node = node.next;
}
return map.get(head);
}
- Rotate List
思路：
注意到k的值可能比链表长度大，所以要先求链表长度length，然后k=k%length，在让指针走到length - k - 1处即可。
代码：
public static ListNode rotateRight(ListNode head, int k) {
if (head == null) return head;
int length = 0;
ListNode p = head;
while (p.next != null) {
length++;
p = p.next;
}
p.next = head;
length++;
k = k % length;
k = length - k - 1;
p = head;
while (k-- > 0) {
p = p.next;
}
head = p.next;
p.next = null;
return head;
}
