目录
链表提升
经典笔试题：反转链表、回文链表、链表带环、复杂链表的复制
1、反转链表
给定单链表的头节点?head?，请反转链表，并返回反转后的链表的头节点。
思路1：暴力解决
直接将1->NULL 2->1 3->2 4->3 5->4?
思路2：头插法
代码：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
while(cur)
{
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
};2、回文链表
给定一个链表的?头节点?head?，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
思路1：利用容器栈，将链表每个节点存入栈，然后弹出之后与原链表比较
思路2：利用快慢指针，在链表笔试题目中，快慢指针的思路十分重要
让慢指针走一步，快指针走两步，当快指针走到尾或者尾的前一个的时候，慢指针走到中间部分，然后可以从中间部分将后续链表反转，然后再从头节点出发比较。优点：不需要利用额外的容器空间。
代码如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL) return NULL;
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
while(cur)
{
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
bool isPalindrome(ListNode* head) {
struct ListNode* fast = head;
struct ListNode* slow = head;
struct ListNode* cur = head;
if(head == NULL) return false;
if(head->next == NULL) return true;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
struct ListNode* newhead = reverseList(slow);
while(cur && newhead)
{
if(cur->val != newhead->val)
{
return false;
}
cur = cur->next;
newhead = newhead->next;
}
return true;
}
};?3、链表带环
给定一个链表的头节点 ?head?，返回链表开始入环的第一个节点。?如果链表无环，则返回?null。
?首先要明确链表带环只有上图一种情况，因为只有一个next指针。
分析是否带环
判断链表是否带环本质上是一个追击问题，让慢指针走一步，快指针走两步，快指针先进环，当满指针进环的时候，快指针可能走了很远也可能走了一点距离，总之就是当慢指针进环的时候，快指针距离慢指针有一定的距离x，然后继续走，慢指针和快指针每继续走一步，这个距离x就会-1，最终快指针一定会追上慢指针，当追上的时候就说明链表一定带环，如果快指针走到了NULL，说明链表不带环。
扩展：如果fast走N步，一定会和slow相遇？? ? ? ? 不一定！
这个就是追击问题的扩展，需要自己写表达式分析，理解了上面的问题自己扩展便能解决。
分析入环点：
?由上图可知，当快指针与慢指针相遇的时候，此时慢指针继续走到入环点的距离等于从头节点走到入环点的距离。所以解决入环点问题，当slow和fast相遇的时候，让一个节点从头节点走，然后slow继续走，slow和从头节点走的指针相遇的点就是入环点。
代码如下：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
//相遇
ListNode* meet = slow;
//公式证明，从相遇点出发，同时一个从头节点出发，同时走，最终会在入环点相遇
while(meet != head)
{
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}
};4、复杂链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的?深拷贝。?深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
?思路1：利用容器哈希表，每次遍历一个节点就放在容器中，并且contain，检测是否容器中存在，如果链表带环，第一个contain到的节点就是入环点。
思路2：复制一个copy链表，将每一个节点链接在原链表相同节点后，如7->7'->13->13'，需要复制的节点的random是原节点的random的next节点，next节点同理，但是要记住还原原链表。
class Solution {
public:
Node* copyRandomList(Node* head) {
//1.复制一个copy链表，将每一个节点链接在原链表相同节点后，如7->7'->13->13';
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;
}
//2.制造随即指针；
cur=head;
while(cur)
{
struct Node* copy=cur->next;
if(cur->random==NULL)
copy->random=NULL;
else
copy->random=cur->random->next;
cur=copy->next;
}
//3.将copy链表断开，然后将copy尾插至新的链表copyHead中；
cur=head;
struct Node *copyHead=NULL,*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;
}
};