24. 两两交换链表中的节点
解析：
基础题，主要是要把握边界条件：由题可得，交换的节点两两一组，每交换完成一对，问题规模减2，也就是只剩一个或不剩节点时交换便结束。
在这里，我们引入一个虚拟头节点，这样所有的交换操作便得到统一。
每一对节点交换一次，不开辟额外空间，因此时间复杂度O(n)，空间复杂度O(1)。
-
class
Solution {
-
public:
-
ListNode* swapPairs(ListNode* head) {
-
ListNode* dummy_head =
new
ListNode(
-1, head);
//虚拟头节点
-
if(head ==
nullptr || head->next ==
nullptr)
return head;
//边界条件先判断
-
ListNode* cur2 = head->next;
-
ListNode* cur1 = head;
-
ListNode* pre = dummy_head;
//两个需要交换的节点，及前节点，共三个节点
-
while(cur1 && cur2){
-
cur1->next = cur2->next;
-
cur2->next = cur1;
-
pre->next = cur2;
-
-
pre = cur1;
-
if(cur1->next && cur1->next->next){
//若只剩1个或不剩 则退出交换
-
cur2 = cur1->next->next;
-
cur1 = cur1->next;
-
}
-
else {
-
break;
-
}
-
}
-
head = dummy_head->next;
//头节点还原
-
delete dummy_head;
-
return head;
-
}
-
};
19.删除链表的倒数第N个节点
解析：
本题以普通办法处理的话就是先遍历一遍，确定链表长度，再遍历一遍，实施删除。虽然不会到O(n^2)的复杂度，仍为线性，但是连续遍历两遍不免让人觉得不快。
因此此类问题，同样可以借鉴双指针法，一前一后不回溯的遍历链表，让前后指针距离保持 n 的距离，那么当后指针到达链表尾的时候，我们自然而然可以靠前指针确定删除位置，且该算法只需一遍遍历。
-
/**
-
* Definition for singly-linked list.
-
* struct ListNode {
-
* int val;
-
* ListNode *next;
-
* ListNode() : val(0), next(nullptr) {}
-
* ListNode(int x) : val(x), next(nullptr) {}
-
* ListNode(int x, ListNode *next) : val(x), next(next) {}
-
* };
-
*/
-
class
Solution {
-
public:
-
ListNode* removeNthFromEnd(ListNode* head, int n) {
-
ListNode* dummy_head =
new
ListNode(
-1,head);
-
ListNode* p = dummy_head;
-
ListNode* q = dummy_head;
-
int kick_off =
0;
-
while(kick_off < n && p->next){
//先让p指针先行，确定q指针何时行动
-
p = p->next;
-
kick_off++;
-
}
-
while(p->next){
//同步行动，直至p指针到最后一个节点，q指针离p n 个位置远
-
p = p->next;
-
q = q->next;
-
}
-
ListNode *tmp = q->next;
-
q->next = q->next->next;
//实施删除
-
-
if(dummy_head->next){
//判断一下是否链表就一个节点，且已被删除
-
head = dummy_head->next;
-
}
-
else{
-
head =
nullptr;
-
}
-
delete tmp;
// 回收要删除的节点
-
delete dummy_head;
//回收虚拟头
-
return head;
-
}
-
};
160.链表相交
解析：
这道题需要巧妙利用到一个思维，也就是链表尾对齐的思维。
如图：若两个链表有相交点，则该交点后的节点均为同一个节点，也就是它们是尾部相等的。所以如果我们能找到长表较之于短表表头的中间位置（等长的位置），然后顺序同步一对一对节点的比较是否相等，便能找到第一个相同的节点，且时间复杂度能控制在O（m+n）。
-
/**
-
* 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) {
-
ListNode* qq = headA;
-
int lenA =
1;
-
int lenB =
1;
-
ListNode* pp = headB;
-
while(qq->next){
//计算A的长度
-
qq = qq->next;
-
lenA++;
-
}
-
while(pp->next){
//计算B的长度
-
pp = pp->next;
-
lenB++;
-
}
-
ListNode* q = headA;
-
ListNode* p = headB;
-
if(lenA < lenB){
// 让q指向较长的链表的表头
-
int tmp = lenA;
-
ListNode* _tmp = q;
-
lenA = lenB;
-
lenB = tmp;
-
q = p;
-
p = _tmp;
-
}
-
int offset = lenA - lenB;
-
while(offset >
0 ){
//想象两个不等长的链表，由末尾对齐，将较长的链表的指针遍历到与较短的链表表头节点对齐
-
q = q->next;
-
offset--;
-
}
-
while(q != p && q){
//开始判等
-
q = q->next;
-
p = p->next;
-
}
-
return q;
-
}
-
};
142.环形链表II
解析：
该题涉及到一个数学推理，详情见卡哥：代码随想录
-
/**
-
* Definition for singly-linked list.
-
* struct ListNode {
-
* int val;
-
* ListNode *next;
-
* ListNode(int x) : val(x), next(NULL) {}
-
* };
-
*/
-
class
Solution {
-
public:
-
ListNode *detectCycle(ListNode *head) {
-
ListNode* p = head;
-
ListNode* q = head;
-
while( q && q->next){
-
p = p->next;
-
q = q->next->next;
-
if(p == q){
-
ListNode* pp = head;
-
ListNode* qq = q;
-
while(pp != qq){
-
pp = pp->next;
-
qq = qq->next;
-
}
-
return qq;
-
}
-
}
-
return
NULL;
-
}
-
};
转载：https://blog.csdn.net/sunnanhunan/article/details/128506857
查看评论