链表系列文章(二)

上一篇文章实现了链表的基本数据结构，这一篇谈一谈关于链表的一些有趣的题目

首先给出链表节点的数据结构

1 struct ListNode {
2     int var;
3     ListNode *next;
4     ListNode(int v = 0 ) : var(v), next(NULL) {  }
5 };

1. 删除链表的倒数第K个节点

例如：给定链表：1->2->3->4->5, n = 5, 返回2->3->4->5

方法一：常规做法，两次扫描，第一次扫描得到链表的长度，然后求得待删除节点的正向索引，第二次扫描删除节点

时间复杂度O(n), 空间复杂度O(1)

 1 ListNode *removeNthNodeFromEndOfList(ListNode *head, int k) {
 2     if( !head || k < 1 ) return NULL;
 3     int len = 0;
 4     ListNode *p = head, newhead(-1);
 5     newhead.next = p;
 6     for( ; p; p = p->next ) len++;//第一遍扫描,得到链表长度
 7     k = len - k;//得到正向索引的前一个节点的索引
 8     if(k < 0) return NULL;
 9     p = &newhead;
10     while( k-- ) p = p->next;//第二遍扫描，定位待删除节点的前一个节点
11     
12     ListNode *tmp = p->next;
13     p->next = tmp->next;
14     delete tmp;
15     return newhead.next;
16 }

方法二：两个指针, 第一个指针先走K步，然后两个指针同时走，当第二个指针走到链表尾时，第一个指针指向的节点就是要删除的节点

时间复杂度O(n), 空间复杂度O(1)

 1 ListNode *removeNthNodeFromEndOfList(ListNode *head, int k) {
 2     if(!head || k < 1)    return NULL;
 3     ListNode newhead(-1), *p = &newhead, *q = &newhead;
 4     newhead.next = head;      
 5     while( k-- && q ) q = q->next; //q->next指向正向第k个节点
 6     if( !q ) return NULL;
 7     while( p && q->next ) { p = p->next; q = q->next; }//p->next就是要删除的节点
 8     q = p->next;
 9     p->next = q->next;
10     delete q;
11     return newhead.next;
12 }

2. 复制带随机指针的链表，随机指针要么指向链表中的节点要么为空

1 struct RandomListNode {
2     int var;
3     RandomListNode *next, *random;
4     RandomListNode(int v) : var(v), next(NULL), random(NULL) { }
5 };

方法一：常规做法，先扫面一遍链表复制next指针；然后对于每个节点，定位随机节点在链表中的索引，然后复制每个random节点时，通过扫描next指针

得到定位索引对应的节点，将random指针指向该节点

时间复杂度O(n²), 空间复杂度O(n)

 1 RandomListNode *copyRandomList(RandomListNode *head) {
 2     if( !head ) return NULL;
 3     int n = 0;
 4     RandomListNode *p = head, newhead(-1), r = &newhead;
 5     for( ; p; p = p->next ) {//扫描链表，复制next指针,同时记录链表长度
 6         r->next = new RandomListNode(p->var);
 7         r = r->next; n++;
 8     }
 9     r = &newhead;
10     for(p = head; p; p = p->next) {//循环复制random指针
11         if(NULL == p->random)
12             r->next->random = NULL;
13         else if(p->random == p)
14             r->next->random = r->next;
15         else {//指向链表中的其它节点
16             int k = n;
17             RandomListNode *q = p->random;
18             RandomListNode *h = newhead.next;
19             while(q) {k--; q = q->next;}//random在源链表中的正向索引
20             while(k--) {h = h->next;}//在复制链表中找到该节点
21             r->next->random = h;
22         }
23         r = r->next;
24     }
25     return newhead.next;
26 }

方法二：将复制链表的节点一一插入到源链表的对应节点后：

如源链表(只显示next指针)：s1->s2->s3->s4

插入后：s1->d1->s2->d2->s3->d3->s4->d4，比如要复制d1的random指针，只需d1->random = s1->random->next即可

时间复杂度O(n), 空间复杂度O(n)

 1 RandomList *copyRandomList(RandomListNode *head) {
 2     if( !head ) return NULL;
 3     RandomListNode newhead(-1);
 4     for( RandomListNode* p = head; p != NULL ) { //一一插入复制链表节点到对应源链表节点后
 5         RandomListNode* q = new RandomListNode(p->var);
 6         q->next = p->next;
 7         p->next = q;
 8         p = q->next;
 9     }
10     for( RandomListNode* p = head; p != NULL ) {//复制random指针
11         if (p->random != NULL)
12             p->next->random = p->random->next;
13         p = p->next->next;
14     }
15     for( RandomListNode* p = head, *d_p = &newhead; p != NULL ) {//恢复两个链表
16         d_p->next = p->next;
17         d_p = d_p->next;
18         p->next = p->next->next;
19         p = p->next;
20     }
21     return newhead.next;
22 }

3. 判断链表是否有环，如果有，找到交点

判断有环：

方法一：hash，用hash表记录每个节点的地址，当第一次遇到hash值存在时，表明相交，同时找到了第一个节点，否则如果走到空，则无交点

时间复杂度O(n), 空间复杂度O(n)

方法二：快慢指针，fast指针每次走两步，slow指针每次走一步，因此fast指针相对slow指针每次走一个，如果有环，必然在有限步相交，至于判断交点，参考博文：

http://www.cnblogs.com/carlsama/p/4127201.html

由于本人水平有限，文章中难免有不让和错误之处，欢迎大家批评指正，愿共同进步！！！