//leetcode中还有花样链表题，这里几个例子，冰山一角
- 求单链表中结点的个数----时间复杂度O（n）
这是最最基本的了，应该能够迅速写出正确的代码，注意检查链表是否为空。参考代码如下：
public static int getListLength(Node head) {
// 注意头结点为空情况
if (head == null) {
return 0;
}
int len = 0;
Node cur = head;
while (cur != null) {
len++;
cur = cur.next;
}
return len;
}
- 将单链表反转----时间复杂度O（n）(也可以先inplace的翻转，再遍历，空间复杂度降到O(1))
- 从头到尾遍历原链表，每遍历一个结点，将其摘下放在新链表的最前端。
- 如果链表为空或只有一个节点，无需反转，直接返回原链表表头。
注意链表为空和只有一个结点的情况。参考代码如下：
public static Node reverseList(Node head) {
if (head == null || head.next == null) {
return head;
}
Node reHead = null; // 反转后新链表最前面的node
Node cur = head;
while (cur != null) {
Node preCur = cur; // 用preCur保存住对要处理节点的引用
cur = cur.next; // cur更新到下一个节点
preCur.next = reHead; // 更新当前节点的next引用，当前.next指向 翻转后链表最前面的node ==>当前节点成为翻转后链表最前面的node
reHead = preCur; // reHead更新
}
return reHead;
}
- leetcode例题
206. Reverse LinkedList
没做过一上来感觉不太好想，有个视频，看到一半恍然大悟：https://www.youtube.com/watch?v=sYcOK51hl-A
这类题都开始要求用iteration写一次再用recursive写一个
//假设1->2->3->4,先从head=1开始，要翻转，最后一个会变成head，所以head一步一步向后挪，每一步也一起翻转指向
public class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while(head!=null){
ListNode nextHead = head.next;
head.next = prev;
prev=head;
//这里得到的prev即下一个head前面的数，也就是下一个head要指向的数，当head=最后一个node（tail）时，prev=tail，循环结束
head = nextHead;
}
return prev;
}
//recursive
public ListNode reverseList(ListNode head) {
return reverseRecursive(head,null);
}
public ListNode reverseRecursive(ListNode head,ListNode prev){
if(head==null) return prev;
ListNode nextHead = head.next;
head.next=prev;
//下面传参其实就相当于这两句：prev=head;head = nextHead;
return reverseRecursive(nextHead,head);
}
}
92. Reverse Linked List II
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
根据题中的例子，第二个for循环开始
loop1:
1 --> 2 --> 3 --> 4 --> 5 --> NULL
p c n
cur.next = next.next;
2 --> 4
next.next = prev.next;
3 --> 2
prev.next = next;
1 --> 3
==> 1 --> 3 --> 2 --> 4 --> 5 --> NULL
p c n
loop2:
cur.next = next.next;
2 --> 5
next.next = prev.next;
4 --> 3
prev.next = next;
1 --> 4
==> 1 --> 4 --> 3 --> 2 --> 5 --> NULL
public ListNode reverseBetween(ListNode head, int m, int n) {
if(m == n) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode cur = head;
//在reverse之前的部分平移
for(int i = 0; i < m - 1; i++){
prev = prev.next;
cur = cur.next;
}
for(int i = 0; i < n - m; i++){
ListNode next = cur.next;
cur.next = next.next;
next.next = prev.next;
prev.next = next;
}
return dummy.next;
}
- 查找单链表中的倒数第K个结点（k > 0）----时间复杂度O（n）
- 最普遍的方法是，先统计单链表中结点的个数，然后再找到第（n-k）个结点。注意链表为空，k为0，k为1，k大于链表中节点个数时这三种情况情况。代码不写了。
- 另一个思路主要就是使用两个指针，先让前面的指针走到正向第k个结点，这样前后两个指针的距离差是k-1，之后前后两个指针一起向前走，前面的指针走到最后一个结点时，后面指针所指结点就是倒数第k个结点。
19. Remove Nth Node From End of List
walker and runner, init walker,runner both as dummy, move runner n steps, so that the gap between runner and walker =n, then move runner and walker together, when runner get to the end of List, walker is before the nth from the end node, walker.next=walke.next.next， skip original walker.next
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode walker = dummy;
ListNode runner = dummy;
// after for loop, gap between runner and walker =n
for(int i = 1; i <= n; i++){
runner = runner.next;
}
while(runner.next!=null){
runner = runner.next;
walker = walker.next;
}
walker.next=walker.next.next;//skip nth node
return dummy.next;
}
- 查找单链表的中间结点----时间复杂度O（n）
此题可应用于上一题类似的思想。也是设置两个指针，只不过这里是，两个指针同时向前走，walker one step each time，runner two steps each time，runner get to the end, walker==mid，即第（n/2+1）个结点。还是分三种情况：链表结点个数为1和2的情况和其他。
public static Node getMiddleNode(Node head) {
if (head == null || head.next == null) {
return head;
}
Node walker = head; ]
Node runner = head;
// 前面指针每次走两步，直到指向最后一个结点，后面指针每次走一步
while (walker.next != null) {
walker = walker.next;
runner = runner.next;
if (runner.next != null) {
runner = runner.next;
}
}
return walker;
}
- 从尾到头打印单链表----时间复杂度O（n）
对于这种颠倒顺序的问题，我们应该就会想到栈，后进先出。所以，这一题要么自己使用栈，要么让系统使用栈，也就是递归。注意链表为空的情况。
public static void reversePrintListStack(Node head) {
Stack<Node> s = new Stack<Node>();
Node cur = head;
while (cur != null) {
s.push(cur);
cur = cur.next;
}
while (!s.empty()) {
cur = s.pop();
System.out.print(cur.val + " ");
}
}
/**
使用递归（优雅！）
*/
public static void reversePrintListRec(Node head) {
if (head == null) {
return;
} else {
reversePrintListRec(head.next);
System.out.print(head.val + " ");
}
}
- Merge two sorted linked list----时间复杂度为O（max(len1, len2)）,O（1）的空间
已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
这个类似归并排序。尤其注意两个链表都为空，和其中一个为空时的情况。
21. Merge Two Sorted Lists
还是iteration和recursion,iteration代码太长了，由此可见递归的好处，代码简介易懂
iteration注意 l1,l2挨个merge的时候为了方便，l1,l2在merge后指向自己next，即后移，同时head即新链表的当前node也后移，另外这里也是head不确定的情况，所以用dummy
//recursion
public ListNode mergeTwoLists(ListNode l1, ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
//iteration
public static Node mergeSortedList(Node head1, Node head2) {
// 其中一个链表为空的情况，直接返回另一个链表头，O(1)
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
Node mergeHead = null;
// 先确定下来mergeHead是在哪里
if (head1.val < head2.val) {
mergeHead = head1;
head1 = head1.next; // 跳过已经合并了的元素，指向已merge的node的next
mergeHead.next = null; // 断开mergeHead和后面的联系
} else {
mergeHead = head2;
head2 = head2.next;
mergeHead.next = null;
}
Node mergeCur = mergeHead;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
mergeCur.next = head1; // 把找到较小的元素合并到merge中
head1 = head1.next; // 跳过已经合并了的元素
mergeCur = mergeCur.next; // 找到下一个准备合并的元素
mergeCur.next = null; // 断开mergeCur和后面的联系
} else {
mergeCur.next = head2;
head2 = head2.next;
mergeCur = mergeCur.next;
mergeCur.next = null;
}
}
// 合并剩余的元素，这个很重要，而且大部分merge算法最后都需要merge剩余东西这一步
if (head1 != null) {
mergeCur.next = head1;
} else if (head2 != null) {
mergeCur.next = head2;
}
return mergeHead;
}
23. Merge k Sorted Lists
根据priority queue的特性，我们可以通过重写compare方法利用priority queue实现，还有dummy，从后向前拼接。
和下面sort里179一样，都重写了compare。一个是sort方法内，一个是priority queue
public ListNode mergeKLists(ListNode[] lists) {
if (lists==null||lists.length==0) return null;
PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.length,new Comparator<ListNode>(){
@Override
/*
1. 这里compare方法可以直接return n1.val-n2.val;
*/
public int compare(ListNode n1, ListNode n2){
if(n1.val<n2.val) return -1;
else if(n1.val==n2.val) return 0;
else return 1;
}
});
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
for(ListNode n:lists){
if(n!=null) queue.add(n);
}
while(!queue.isEmpty()){
tail.next = queue.poll();
tail=tail.next;
if(tail.next!=null){
queue.add(tail.next)；
}
}
return dummy.next;
}
- 判断一个单链表中是否有环----时间复杂度为O（n）
这里也是用到两个指针。如果一个链表中有环，也就是说用一个指针去遍历，是永远走不到头的。因此，我们可以用两个指针去遍历，一个指针一次走两步，一个指针一次走一步，如果有环，两个指针肯定会在环中相遇。
141. Linked List Cycle
- 用双指针的思路，walker moves step by step. runner moves two steps at time. if the Linked List has a cycle walker and runner will meet at some
point. - 解法代码下一题中其实是包含的，但我还是把这个代码贴出来了，因为判定条件那里需要注意，这道题的写法是，先判断了head==null，之后while中判断runner.next和runner.next.next，个人理解是runner跑的快，需要注意判断runner而不是walker。下一题的写法看起来跟这个不同，其实一样
public boolean hasCycle(ListNode head) {
if(head==null) return false;
ListNode walker = head;
ListNode runner = head;
// runner跑的快，在前面，所以判断runner.next, runner.next.next
while(runner.next!=null&&runner.next.next!=null){
walker = walker.next;
runner = runner.next.next;
if(walker==runner) return true;
}
return false;
}
142. Linked List Cycle2
关于判定条件的一个问题上道题中解释了
这个题目的思路不太好想，discuss中有一个很好的解释，贴过来，其中关键的两点是，walker走过的距离和cycle长度的关系，以及walker,runner相遇之后再通过head和walker一齐走，相遇点是cycle起点这层关系
Definitions:
Cycle = length of the cycle, if exists.
C is the beginning of Cycle, S is the distance of slow pointer from C when slow pointer meets fast pointer.
Distance(slow) = C + S, Distance(fast) = 2 * Distance(slow) = 2 * (C + S). To let slow poiner meets fast pointer, only if fast pointer run 1 cycle more than slow pointer. Distance(fast) - Distance(slow) = Cycle
=> 2 * (C + S) - (C + S) = Cycle
=> C + S = Cycle
=> C = Cycle - S
=> This means if slow pointer runs (Cycle - S) more, it will reaches C. So at this time, if there's another point2(we use head Here) running from head
=> After C distance, point2 will meet slow pointer at C, where is the beginning of the cycle.
public ListNode detectCycle(ListNode head) {
ListNode walker = head;
ListNode runner = head;
//这里不加runner.next.next!=null也ac
while(runner!=null&&runner.next!=null&&runner.next.next!=null){
runner = runner.next.next;
walker = walker.next;
if(runner==walker){
while(head!=walker){
head = head.next;
walker = walker.next;
}
return walker;
}
}
return null;
}
- 判断两个单链表是否相交----时间复杂度为O(len1+len2)，因为只需要一个额外指针保存最后一个节点地址，空间复杂度为O(1)。
如果两个链表相交于某一节点，那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说，如果两个链表相交，那么最后一个节点肯定是共有的。先遍历第一个链表，记住最后一个节点，然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则不相交。
public static boolean isIntersect(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return false;
}
Node tail1 = head1;
// 找到链表1的最后一个节点
while (tail1.next != null) {
tail1 = tail1.next;
}
Node tail2 = head2;
// 找到链表2的最后一个节点
while (tail2.next != null) {
tail2 = tail2.next;
}
return tail1 == tail2;
}
- 求两个单链表相交的第一个节点----时间复杂度，O(len1+len2)
对第一个链表遍历，计算长度len1，同时保存最后一个节点的地址。
对第二个链表遍历，计算长度len2，同时检查最后一个节点是否和第一个链表的最后一个节点相同，若不相同，不相交，结束。
两个链表均从头节点开始，假设len1大于len2，那么将第一个链表先遍历len1-len2个节点，此时两个链表当前节点到第一个相交节点的距离就相等了，然后一起向后遍历，知道两个节点的地址相同。
*
* ---- len2
* |__________
* |
* --------- len1
* |---|<- len1-len2
*/
public static Node getFirstCommonNode(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
int len1 = 1;
Node tail1 = head1;
while (tail1.next != null) {
tail1 = tail1.next;
len1++;
}
int len2 = 1;
Node tail2 = head2;
while (tail2.next != null) {
tail2 = tail2.next;
len2++;
}
// 不相交直接返回NULL
if (tail1 != tail2) {
return null;
}
Node n1 = head1;
Node n2 = head2;
// 略过较长链表多余的部分
if (len1 > len2) {
int k = len1 - len2;
while (k != 0) {
n1 = n1.next;
k--;
}
} else {
int k = len2 - len1;
while (k != 0) {
n2 = n2.next;
k--;
}
}
// 一起向后遍历，直到找到交点
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
160. Intersection of Two Linked Lists
- 一个general的方法, 比较两个linked list的长度，把较长的一个链表后移几位，从长度和另一链表相等处开始比较node是否相同。
一开始在想相交之后还会不会分开，比如一开始就相交，那长度不等情况下先向后移就说不过去了，但是这里应该是利用了链表特性，每个node都指向另一个node，所以相交之后就一定都一样了。 - 一个很机智的方法，感觉用到了类似single linked list中判断是否有cycle时候用的runner 和walker双指针的方法，这个题中的“双指针”总会在intersection处相遇或者没有intersection在最后的null相遇.
disscuss区大神的分析: - use two iterations here. In the first iteration, we will reset the pointer of one linkedlist to the head of another linkedlist after it reaches the tail node. In the second iteration, we will move two pointers until they points to the same node. Our operations in first iteration will help us counteract the difference.
So if two linkedlist intersects, the meeting point in second iteration must be the intersection point. If the two linked lists have no intersection at all, then the meeting pointer in second iteration must be the tail node of both lists, which is null - The problem description especially required the code to run in O(n) time and O(1) space. Thus I came up with the most direct way.
Just count the lengths of both lists, set two pointers from the list heads, align them to equipotential position and move'em forward until they coincide.
That would be the answer we seek.
Time complexity should be O(n + m), if you name the lengths of both lists to be "n" and "m". Extra space required is O(1). - Notice：只贴一下第二个方法，第一个方法很简单，分别遍历链表直到空，通过counter获取长度，然后通过两个长度差值移动指向较长链表的node的位置，在等长之后比较node是否相同，是就返回该node。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode a = headA;
ListNode b = headB;
while( a != b){
a = a == null? headB : a.next;
b = b == null? headA : b.next;
}
return a;
}
- 已知一个单链表中存在环，求进入环中的第一个节点
上面贴的leetcode142
首先判断是否存在环，若不存在结束。在环中的一个节点处断开（当然函数结束时不能破坏原链表），这样就形成了两个相交的单链表，求进入环中的第一个节点也就转换成了求两个单链表相交的第一个节点。参考代码如下：
/**
* 求进入环中的第一个节点 用快慢指针做（本题用了Crack the Coding Interview的解法，因为更简洁易懂！）
*/
public static Node getFirstNodeInCycle(Node head) {
Node slow = head;
Node fast = head;
// 1） 找到快慢指针相遇点
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // Collision
break;
}
}
// 错误检查，这是没有环的情况
if (fast == null || fast.next == null) {
return null;
}
// 2）现在，相遇点离环的开始处的距离等于链表头到环开始处的距离，
// 这样，我们把慢指针放在链表头，快指针保持在相遇点，然后
// 同速度前进，再次相遇点就是环的开始处！
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
// 再次相遇点就是环的开始处
return fast;
}
- 给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted----总体的平均时间复杂度还是O(1)
对于删除节点，我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点，这种情况需要遍历找到该节点的前一个节点，时间复杂度为O(n)。对于链表，链表中的每个节点结构都是一样的，所以我们可以把该节点的下一个节点的数据复制到该节点，然后删除下一个节点即可。要注意最后一个节点的情况，这个时候只能用常见的方法来操作，先找到前一个节点，但总体的平均时间复杂度还是O(1)。参考代码如下：
public void delete(Node head, Node toDelete){
if(toDelete == null){
return;
}
if(toDelete.next != null){ // 要删除的是一个中间节点
toDelete.val = toDelete.next.val; // 将下一个节点的数据复制到本节点!
toDelete.next = toDelete.next.next;
}
else{ // 要删除的是最后一个节点！
if(head == toDelete){ // 链表中只有一个节点的情况
head = null;
}else{
Node node = head;
while(node.next != toDelete){ // 找到倒数第二个节点
node = node.next;
}
node.next = null;
}
}
}
规律总结
- DummyNode
做链表题目时，如果head可能被改变，我们需要创建一个虚拟节点，叫DummyNode，把头部挂在它的后面。这样就算头部变化了之后，只要返回DummyNode.next就能轻松得到新头部。 - Merge LinkedList是相当基础的题目，merge的半成品代码上面也有提到。
- Reverse linkedList最简单的写法就是创建DummyNode，然后把旧的链表不断插入到DummyNode的后面，就能轻松地返回链表了。
- 操作链表的时候，我们经常会改变某些Node。如果后面还需要再用到被改变掉节点的原始值，请一定记得用tmp先把它保存起来。
