文章目录
- 1.[链表分割](https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking)
- 2.[链表的回文结构](https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking)
- 3.[相交链表](https://leetcode.cn/problems/intersection-of-two-linked-lists/description/)
- 4.[环形链表](https://leetcode.cn/problems/linked-list-cycle/description/)
1.链表分割
1.1 题目要求
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
1.2 哨兵位法
创建两个哨兵位节点，一个用来存放val小于x的节点，一个存放val大于等于x的节点。
因为我们是顺序遍历，不会打乱原来的数据顺序，满足条件直接按要求放就可以了。最后再把存放val大于等于x的链表接到val小于x的链表后面就可以了。
但是最后会有一个坑！
当我们把两个链表连接后，可不能忘了head2（存放val大于等于x的节点）的最后一个节点可能不是指向NULL，就可能构成一个环，导致程序出错。
为什么会造成这种情况呢？
因为我们把节点链接到相应链表时没有除了节点的next，虽然后面会通过tail来处理next链接的问题，但是最后一个节点是做不到的。解决方法就是在最后处理一下，把tail2的next置为NULL就解决问题了。
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// write code here
ListNode* head1 = (ListNode*)malloc(sizeof(ListNode));
ListNode* head2 = (ListNode*)malloc(sizeof(ListNode));
ListNode* tail1 = head1;
ListNode* tail2 = head2;
ListNode* cur = pHead;
while(cur)
{
if(cur->val<x)
{
tail1->next = cur;
tail1 = tail1->next;
}
else
{
tail2->next = cur;
tail2 = tail2->next;
}
cur = cur->next;
}
tail1->next = head2->next;
tail2->next = NULL;
return head1->next;
}
};
2.链表的回文结构
2.1 题目要求
判断链表是否是回文链表，是返回true，不是返回false。
2.2 快慢指针加反转链表
因为这个链表是单向的，无法做到像字符串那样，从两边往中间遍历来确定是否回文。
那么既然要判断链表是否的回文链表，肯定要先找到中间啊，找到中间就能找到两条相同的链表，你需要管节点数是单数的情况，中间的节点是不会影响最后的结果的。
在找到中间节点时，要记得把让中间节点的前前一个节点的next指向NULL。方便后续的比较。
通过快慢指针我们找到了链表的中间，但是怎么比较的，单链表可不能向前遍历。有什么办法吗？
当然了，让链表反转不就好了，这样的话就方便比较了，我们把链表的后一半反转，然后拿到反转后的头节点。
最后就是遍历比较了，一旦出现不同就返回false，都相同则返回true。
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
//先利用快慢指针法找到链表的中间
//然后利用链表的反转将后半部分反转
//最后在开始比较
ListNode* fast = A;
ListNode* slow = A;
ListNode* prev = NULL;
while(fast&&fast->next)
{
fast = fast->next->next;
prev = slow;
slow = slow->next;
}
//slow即为链表中间
//开始反转
prev->next = NULL;
prev = NULL;
ListNode* cur = slow;
while(cur)
{
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
ListNode* l1 = A;
ListNode* l2 = prev;
while(l1&&l2)
{
if(l1->val!=l2->val)
return false;
l1 = l1->next;
l2 = l2->next;
}
return true;
}
};
3.相交链表
3.1 题目要求
找到A,B的第一个共同节点并返回，没有就返回NULL
3.2 双指针消除长度差
这里我借用题解里的一位大佬画的图大佬题解
有了这张图片，相信也不用太多解释。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* a = headA;
struct ListNode* b = headB;
while(a!=b)
{
a = a!=NULL?a->next:headB;
b = b!=NULL?b->next:headA;
}
return a;
}
3.3 哈希法
其实这太题还有一种解法，哈希法，但是用C语言就比较不好写了。感兴趣的话，可以看一下下面的c++代码。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set<ListNode *> visited;
ListNode *temp = headA;
while (temp != nullptr) {
visited.insert(temp);
temp = temp->next;
}
temp = headB;
while (temp != nullptr) {
if (visited.find(temp)!=visited.end()) {
return temp;
}
temp = temp->next;
}
return nullptr;
}
};
4.环形链表
4.1 题目要求
找出链表中存在的环，如果存在就返回true，不存在就返回false
4.2 快慢指针
利用快慢指针，如果不存在环的话，慢指针永远也追不上快指针，直到快指针走到链表的尽头。
但是如果存在环的话，当慢指针还没进入环时，快指针肯定已经在环里面不断地循环了，而环里面是没有前后之分的，一旦慢指针进入环内，现在我们先想象这两个指针不是跳跃似地运动，而是平移，这样的话，快指针一定是会与慢指针相遇的。
可是如果是跳跃似地这样呢？
也就是为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚
进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。
此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情
况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
大家也可让快指针走3步看看行不行
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(slow == fast)
return true;
}
return false;
}