数据结构链表问题

在算法练习中遇到的链表问题
单链表

1.快慢指针找中点或者某一个位置

class Solution {
public:bool isPalindrome(ListNode* head) {ListNode* slow &＃61; head, *fast &＃61; head, *prev &＃61; nullptr;//快慢指针:使fast指针的前进速度为slow指针的前进速度的两倍&＃xff0c;当fast指到链尾时&＃xff0c;slow指针就指到链表中间结点while (fast && fast->next ){//find mid nodeslow &＃61; slow->next; fast&＃61;fast->next->next;}

2.链表翻转

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *p &＃61; head;//当前指针节点ListNode *pre &＃61; NULL;//前指针节点while (p!&＃61;NULL) { //循环都将当前节点指向它前面的节点&＃xff0c;然后当前节点和前节点后移ListNode* nxt &＃61; p->next;//临时节点&＃xff0c;暂存当前节点的下一节点&＃xff0c;用于后移p->next &＃61; pre;//将当前节点指向它前面的节点pre&＃61;p;//前指针后移p&＃61;nxt; //当前指针后移}return pre;}
};


3 删除链表中的节点
思路&＃xff1a;让要删除的节点的值等于下一个节点的值&＃xff0c;删除之后的节点。&＃xff08;因为&＃xff0c;我们无法访问我们想要删除的节点 之前 的节点&＃xff0c;我们始终不能修改该节点的 next 指针。相反&＃xff0c;我们必须将想要删除的节点的值替换为它后面节点中的值&＃xff0c;然后删除它之后的节点。*&＃xff09;

class Solution {
public:void deleteNode(ListNode* node) {node->val &＃61; node->next->val;node->next &＃61; node->next->next; //修改指针语句—— 链表删除}
};


4.合并链表&＃xff08;1.首尾相连合并链表 2.顺序合并链表&＃xff09;

2.顺序合并链表
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if(l1&＃61;&＃61;NULL)return l2;if(l2&＃61;&＃61;NULL)return l1;ListNode* pa &＃61; l1; ListNode* pb &＃61; l2; ListNode *l3 &＃61; new ListNode(NULL);ListNode* pc &＃61; l3; while(pa&&pb){if(pa->val <&＃61; pb->val){pc->next &＃61; pa;pc&＃61;pa;pa&＃61;pa->next; } else {pc->next &＃61; pb;pc&＃61;pb;pb&＃61;pb->next;}}pc->next &＃61; pa?pa:pb;return l3->next;}
};


5.回文链表
思路&＃xff1a;
//其一&＃xff0c;find mid node 使用快慢指针找到链表中点。
//其二&＃xff0c;reverse 逆序后半部分。
//其三&＃xff0c;check 从头、中点&＃xff0c;开始比较是否相同。


class Solution {
public:bool isPalindrome(ListNode* head) {ListNode* slow &＃61; head, *fast &＃61; head, *prev &＃61; nullptr;//快慢指针:使fast指针的前进速度为slow指针的前进速度的两倍&＃xff0c;当fast指到链尾时&＃xff0c;slow指针就指到链表中间结点while (fast && fast->next ){//find mid nodeslow &＃61; slow->next; fast&＃61;fast->next->next;}while (slow){//reverseListNode* ovn &＃61; slow->next;slow->next &＃61; prev;prev &＃61; slow;slow &＃61; ovn;}while (head && prev){//checkif (head->val !&＃61; prev->val){return false;}head &＃61; head->next;prev &＃61; prev->next;}return true; }
};


6.环形链表&＃xff08;链表中是否有环&＃xff09;****

//141.环形链表
//思路&＃xff1a;快慢指针&＃xff0c;如果慢指针追上快指针则表示有环 返回true 追不上怎表示没环
class Solution {
public:bool hasCycle(ListNode *head) {ListNode *p &＃61; head;ListNode *q &＃61; head;ListNode * nu &＃61; NULL;while(p && p->next){p &＃61; p->next->next;q &＃61; q->next;if(q &＃61;&＃61; p){return true;}}return false;}
};


7.找到入环节点
常见的方法是&＃xff1a;在确定链表有环之后&＃xff0c;慢指针重新指向链表头&＃xff0c;快指针留在相遇处&＃xff1b;然后快慢指针再以每次移动1个节点的速度前进&＃xff0c;最终他们在入环节点相遇。

如图&＃xff0c;设整个链表长度为L&＃xff0c;环长度为R&＃xff0c;且距离具有方向性&＃xff0c;例如CB是C点到B点的距离&＃xff0c;BC是B点到C点的距离&＃xff0c;CB!&＃61;BC。当证明有环时&＃xff0c;fast和slow都顺时针到了B点&＃xff0c;则此时&＃xff1a;
slow走的距离&＃xff1a;AC&＃43;CB
fast走的距离&＃xff1a;AC&＃43;kR&＃43;CB(k&＃61;0,1,2…)
由于fast每次走2个节点&＃xff0c;slow每次走1个节点&＃xff0c;所以&＃xff1a;
2(AC&＃43;CB) &＃61; AC&＃43;kR&＃43;CB
AC&＃43;CB &＃61; k*R
AC&＃43;CB &＃61; (k-1)*R&＃43;R
AC &＃61; (k-1)*R&＃43;R-CB
AC &＃61; (k-1)*R&＃43;BC
从最终的表达式可以看出来&＃xff0c;AC的距离等于绕环若干圈后再加上BC的距离&＃xff0c;也就是说慢指针从A点出发以速度1前进、快指针从B点出发以速度1前进&＃xff0c;则慢指针到C点时&＃xff0c;快指针也必然到了。

function ListNode(x){this.val &＃61; x;this.next &＃61; null;
}
function EntryNodeOfLoop(pHead){if(pHead &＃61;&＃61;&＃61; null)return null;var fast &＃61; pHead;var slow &＃61; pHead;while(fast.next !&＃61;&＃61;null && fast.next.next !&＃61;&＃61; null) {slow &＃61; slow.next;fast &＃61; fast.next.next;if(slow &＃61;&＃61;&＃61; fast)break;}if(fast &＃61;&＃61;&＃61; null || fast.next &＃61;&＃61;&＃61; null)return null;// 有环&＃xff0c;slow重新回到链表头slow &＃61; pHead;// slow和fast重新相遇时&＃xff0c;相遇节点就是入环节点while(slow !&＃61;&＃61; fast) {slow &＃61; slow.next;fast &＃61; fast.next;}return slow;
}


8、判断两个链表是否相交
两种情况&＃xff1a;A&＃xff1b;有环
B&＃xff1b;没环
A:在环里设置一个指针不动&＃xff0c;另一个从头开始移动&＃xff0c;指针相遇则相交。
B&＃xff1a;判断两个链表最后节点是否相同&＃xff0c;相同即相交。

9、 两个链表相交&＃xff0c;求交点。

解法1.用两个stack栈
解法2,求出两个链表长度a&＃xff0c;b&＃xff0c;一个指针从head开始&＃xff0c;一个从head&＃43;|a-b|开始&＃xff0c;相遇即相交。求出交点。