24 两两交换链表中的节点

思路

画图就可以明确实现思路
重点是如果只用一个指针会更方便更新位置，用多个指针可能会更乱

代码

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* _dummyhead = new ListNode (0);_dummyhead->next = head;ListNode* cur = _dummyhead;while (cur->next != NULL && cur -> next -> next != NULL) {ListNode* tmp1 = cur -> next;ListNode* tmp2 = cur->next->next->next;cur -> next = cur->next->next;cur -> next -> next = tmp1;cur -> next -> next -> next = tmp2;cur = cur -> next -> next;}return _dummyhead->next;}
};

总结

1. 画图明确思路
2. 用一个指针
3. 虚拟头结点

19 删除链表的倒数第N个节点

思路

虚拟头结点
双指针

代码

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {// 遍历// 计数器数到n的时候，指向头结点，然后跟着遍历下去ListNode* _dummyhead = new ListNode (0);_dummyhead -> next = head;int count = n;bool flag = false;ListNode* cur = _dummyhead ;ListNode* res = _dummyhead ;while (cur -> next -> next != NULL) {if (count == 1) {flag = true;}if (flag) {res = res -> next;}cur = cur -> next;count --;}ListNode* tmp = res -> next;res -> next = res -> next -> next;delete tmp;return _dummyhead -> next;}
};

总结

1. 使用虚拟头结点会更方便

面试题 02.07 链表相交

思路

将两个链表末端对齐遍历进行寻找

代码

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {int lenA = 0;int lenB = 0;ListNode* curA = headA;ListNode* curB = headB;while (curA != NULL) {lenA++;curA = curA -> next;}while (curB != NULL) {lenB++;curB = curB -> next;}curA = headA;curB = headB;if (lenA < lenB) {swap(lenA,lenB);swap(curA,curB);}int gap = lenA - lenB;while (gap --) {curA = curA -> next;}while (curA != NULL) {if (curA == curB) {return curA;}curA = curA -> next;curB = curB -> next;}return NULL;}
};

总结

1. 交换两个链表：swap(headA, headB)

142 环形链表II

思路

实际上有两问：1. 是否有环；2. 环的入口
快慢指针判断有环：只有在有环的时候，快慢指针才可能相遇
找入口： 一个指针指向链表头，一个指针指向环内相遇点，这两个指针在遍历过程中的相遇点就是环的入口

代码

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while (fast != NULL && fast -> next != NULL) {fast = fast -> next -> next;slow = slow -> next;if (slow == fast) {//相遇ListNode* tmp1 = fast;ListNode* tmp2 = head;while (tmp1 != tmp2) {tmp1 = tmp1 -> next;tmp2 = tmp2 -> next;}return tmp1;}}return NULL;}
};

总结

1. 解题思路比较特殊，应该记下来