链表问题-LeetCode 206、234、160（反转，回文，公共结点）
链表问题-LeetCode 206、234、160（反转，回文，公共结点）
【LeetCode #206】反转链表
反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
解题思路：
递归版与迭代版两种思路，不过形式都一样的！主要循环步骤如下： 使用pre与cur两个指针，进行如下操作
- 使用临时变量储存cur.next，因为下面需要修改，修改后就找不到了
- 将cur的next修改成pre
- pre向后移动，即pre=cur
- cur向后移动，即cur=tmp
递归版就是讲这四个步骤封装成函数，递归调用！
递归版
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur != nullptr){
ListNode* tmp = cur->next; // 储存cur的下一个值，因此下面要改变cur的next
cur->next = pre; // 将cur的next置为pre
pre = cur; // 将pre向后移动
cur = tmp; // 将cur向后移动
}
return pre;
}
};迭代版
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
return reverse(nullptr, head);
}
ListNode* reverse(ListNode* pre, ListNode* cur){
if(cur == nullptr) return pre;
ListNode* tmp = cur->next;
cur->next = pre;
return reverse(cur, tmp); // 相当于pre = cur, cur = tmp
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list/
【LeetCode #234】回文链表
请判断一个链表是否为回文链表。
示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true
解题思路：
回文的判断一般从都是一个从头部，一个从尾部开始判断，元素是否相等。但是本题目中链表为单向链表，因此不可能从尾部开始遍历！ 但是一个显然的思路，可以将这个单向链表从中间截开，将其中一个进行反转，然后再进行判断。反转链表的操作可以参考LeetCode #206
寻找链表的中心节点可以使用快慢指针！核心代码如下： slow = slow->next fast = fast->next ? fast->next->next : fast->next 注意：获取fast->next->next之前一定要判断一下fast->next，防止不存在，导致程序错误。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* slow = head, *fast = head, *pre = nullptr;
while(fast != nullptr){
slow = slow->next;
fast = fast->next ? fast->next->next : fast->next;
}
while(slow != nullptr){
ListNode* tmp = slow->next;
slow->next = pre;
pre = slow;
slow = tmp;
} // 将slow后面的链表反转
while(head && pre){
if(head->val != pre->val){
return false;
}
head = head->next;
pre = pre->next;
}
return true;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-linked-list/
【LeetCode #160】相交链表
解题思路：
首先两个链表的指针pA与pB一起走，并且其指向的地址都不同，循环一直下去到最后，必定有一个较短的链表指针（假设pA）为nullptr，将该指针指向较长链表的头部, pA=headB. 接着继续向后移动，此时还有出现一次较长链表的指针为空的情况，将该指针指（pB）向较短链表的头部，pB=headA. 然后再一起向后移动，直到指向相同位置，跳出循环，并返回指针！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == nullptr || headB == nullptr) return nullptr;
ListNode* pA = headA;
ListNode* pB = headB;
while(pA != pB){
pA = pA == nullptr ? headB : pA->next;
pB = pB == nullptr ? headA : pB->next;
}
return pA;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
腾讯云开发者
