【链表OJ】常见面试题 2

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 hereListNode* 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;
}