回文链表题目分析：

代码实现：

相交链表的题目分析：

代码实现：

思路一：

思路2：（浪漫又难理解）

环形链表的题目分析：

代码实现：

环形链表 || 的题目解析：

代码实现：

思路1：（示意图如下）

思路2：（示意图如下）

复制带随机指针的链表题目分析：

代码实现：

昨天我们看的是链表比较基础的题，今天我们来看下比较新颖的题。

234. 回文链表

回文链表题目分析：

这道题我们看起来比较简单，就是判断是不是回文，我们用的答题思路是：

先找到链表的中间节点，

然后从中间节点向后的链表逆置，

最后两个，一个头指针，一个中间节点的指针，向后遍历，为空停止。

示意图如下：

代码实现：

首先我们找中间节点，然后逆置，这都已经学过了。

struct ListNode* reverseList(struct ListNode* head){    struct ListNode* Newnode = NULL;    struct ListNode* cur = head;    while(cur)    { struct ListNode *tmp = cur->next; cur->next = Newnode; Newnode = cur; cur = tmp;    }    return Newnode;}struct ListNode* middleNode(struct ListNode*head){    struct ListNode* fast = NULL;    struct ListNode* slow = NULL;    fast = slow = head;    while(fast->next && fast->next->next)    { slow = slow->next; fast = fast->next->next;    }    return slow;}bool isPalindrome(struct ListNode* head){    struct ListNode* mid = middleNode(head);    struct ListNode* rhead = reverseList(mid);    while(rhead && head)    { if(rhead->val != head->val) {     return false; } else {    rhead = rhead->next;     head = head->next; }    }    return true;}

1.首先找中间节点。

2.逆置中间节点到最后的结点之间的链表。

3.两个指针一个指向头指针，一个指向中间节点的指针，进行遍历，任何一个结点为空停止。

注意：结点数奇数和偶数都是适用的，我们可以通过上述示意图看出，我们还是注意循环的结束条件，我们想的是结束条件，但是写在循环的限定条件处的是继续条件。

160. 相交链表

相交链表的题目分析：

 我们看到这个题目样式比较简单，就是两个链表求交点，并且为无环链表，思路如下：

思路一：我们可以算出链表长度，求差值，然后让长的链表先走，然后在一起走，如果相等就返回。

思路二（浪漫又抽象）：定义两个指针，一个先走长链表，再走短链表，一个先走短链表，再走长链表，最后会在交点处相遇。

（你走过我走的路，我们最终会相遇，愿天下有情人都返回 true ）

思路三：我们可以把其中一个链表链接起来，变成判断链表带环问题（自己实现哦）

代码实现：

思路一：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB){    int lenA = 1, lenB = 1;    struct ListNode* curA = headA, *curB = headB;    //计算链表长度    while(curA)    { ++lenA; curA = curA->next;    } while(curB)     { ++lenB; curB = curB->next;    } int gap = abs(lenA-lenB);    struct ListNode* longList = headA, *shortList = headB;    if(lenA next;    }    //两个链表同时走，直到遇到相同的节点    while(longList && shortList)    { if(longList == shortList) {     return longList; } else  {     longList = longList->next;     shortList = shortList->next; }    } return NULL;}

1.首先我们先遍历一遍链表，得到两个链表的长度。

2.算出两个链表的差值。

3.使用假设法，求出链表中较长的，然后让长链表走差值步。

4.让两个链表同时走，节点值相等就返回节点，不相等返回NULL，说明没交点。

注意：思路一虽然思想简单，但是实现的过程中很多细节需要注意，比如假设法求较长的链表，比如循环结束条件。

思路2：（浪漫又难理解）

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB){    struct ListNode *pA = headA;    struct ListNode *pB = headB;    if(headA == NULL  || headB == NULL)    { return NULL;    }    while(pA != pB)    { pA = pA == NULL ? headB : pA->next; pB = pB == NULL ? headA : pB->next;    } return pA;}

我们看上述图示来理解，就会方面很多了。

 

注意：我们先要判断这两个链表都要不为空，并且在一个链表走到NULL时，要直接走下一个链表。 

141. 环形链表

环形链表的题目分析：

我们依然可以使用快慢指针追赶的形式来进行解答，快指针一次走2步，慢指针一次走一步，然后快指针先入环，然后慢指针在入环，然后让快慢指针再环内追赶，最后相遇。 

代码实现：

bool hasCycle(struct ListNode *head) {    struct ListNode* fast = head;    struct ListNode* slow = head;    while(fast && fast->next)    { fast = fast->next->next; slow = slow->next; if(fast == slow) {     return true; }    }    return false;}

代码上没什么难点，我们要注意循环的限定条件是快指针为空或者快指针的next为空。

为什么要走两步呢？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚 进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。 此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情 况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

必须快指针走2步才可以，走3步可以吗？

142. 环形链表 II

环形链表 || 的题目解析：

这个题目实际上要我们返回链表的入环点，如果没环就返回NULL。

 

这个题的整体思路是先用快慢指针判断是否链表有环，然后顺带求出快慢指针在环的相遇点，接着我们就分为两种思路：

思路一：

我们把相遇节点保存，在保存它的下一个节点，然后从相遇节点断开，问题转化为求两个链表的相交，求交点。

思路二：我们把相遇点保存，然后遍历，让头结点，和相遇点同时向前走，最后会在入环点相遇。

代码实现：

思路1：（示意图如下）

struct ListNode *detectCycle(struct ListNode *head) {    struct ListNode* fast = head; struct ListNode* slow = head;    while(fast && fast->next)     { slow = slow->next; fast = fast->next->next; if(fast == slow) {     struct ListNode* phead = fast->next;     struct ListNode* p1 = phead;     struct ListNode* p2 = head;     fast->next = NULL;     while(p1 != p2)     {  p1 = p1 == NULL? head: p1->next;  p2 = p2 == NULL? phead: p2->next;     }     return p1; }    }return NULL;}

1.先求相遇点。

2.保存相遇点的next。

3.求两个链表相交。

思路2：（示意图如下）

 

 我们根据上图的逻辑，以及结论是可以写出思路二的代码的。

struct ListNode *detectCycle(struct ListNode *head) {    struct ListNode* fast = head;    struct ListNode* slow = head;    while(fast && fast->next)    { fast = fast->next->next; slow = slow->next; if(fast == slow) {     struct ListNode* meet = fast;   while(head != meet)     {  meet = meet->next;  head = head->next;     }     return meet; }    }     return NULL;    }

138. 复制带随机指针的链表

复制带随机指针的链表题目分析：

这道题也叫做链表的深拷贝，就是有一个链表，他有两个指针，一个指向随机值，一个指向下一个，要求我们拷贝一份这样的链表。 

我们的答题思路是，先在创建每个节点，链接到原节点的后面，然后它的随机指针就是源节点的随机指针的next，然后把拷贝的节点尾插就好啦。

代码实现：

 

struct Node* copyRandomList(struct Node* head) {    struct Node* cur = head;    while(cur)//创建结点链接到后面    { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; copy->next = cur->next; cur->next = copy; cur = copy->next;    }    cur = head;    //链接随机指针 copy->random = cur->random->next    while(cur)    { struct Node* copy = cur->next; if(cur->random == NULL) {     copy->random = NULL; } else {     copy->random = cur->random->next; } cur = copy->next;    }    cur = head;    //尾插    struct Node* copyhead = NULL;    struct Node* copytail = NULL;    while(cur)    { struct Node* copy = cur->next; struct Node* next = copy->next; if(copytail == NULL) {     copyhead = copytail = copy; } else {     copytail->next = copy;     copytail = copytail->next; } cur->next = next; cur = next;    }    return copyhead;}

1.先创建节点，链接到原链表每个节点的后面。

2.然后就是 copy->random = cur->random->next 的理解到位，如果原节点的 random 指为NULL，则 copy->random 也指为 NULL。

3.把 copy 的节点拿下来尾插一个新链表，返回就可以啦。

我们最重要的是明白 copy->random = cur->random->next，这个的由来。