24. 两两交换链表中的节点

题目链接
状态： 一遍过
思路： 使用虚拟节点放在开头，注意盯住三个节点的变化即可

原始代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* dummynode = new ListNode(0);
        dummynode->next = head;
        ListNode *cur = head->next, *pre = head, *h = dummynode;
        while (cur != nullptr) {
            pre->next = cur->next;
            cur->next = pre;
            h->next = cur;
            h = pre;
            pre = pre->next;
            if (pre != nullptr)
                cur = pre->next;
            else break;
        }
        h = dummynode->next;
        delete dummynode;
        return h;
    }
};

改进地点：

  1. 在判断while时可以包含空节点或单一节点，统一化判断
  2. 简化每次交换中节点个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode* cur = dummyHead,* tmp,*tmp1;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            tmp = cur->next; // 记录临时节点
            tmp1 = cur->next->next->next; // 记录临时节点

            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp;          // 步骤二
            cur->next->next->next = tmp1;   // 步骤三

            cur = cur->next->next; // cur移动两位，准备下一轮交换
        }
        cur = dummyHead->next;
        delete dummyHead;
        return cur;
    }
};

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

题目链接

状态：一遍过
思路：1.虚拟节点指向head。2. 快慢指针相隔n个节点。3. 前一个节点的后继为空，则后一个节点即为倒数第n个节点（应删除节点）的前驱节点，故直接删除即可。4.最后释放删除节点和虚拟节点内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummynode =new ListNode(0);
        dummynode->next=head;
        ListNode*p,*q;
        p=q=dummynode;
        while(n--){
            p=p->next;
        }
        while(p->next!=nullptr){
            p=p->next;
            q=q->next;
        }
        p=q->next;
        q->next=p->next;
        delete p;
        p=nullptr;
        q=dummynode->next;
        delete dummynode;
        return q;
    }
};

面试题 02.07. 链表相交

题目链接
状态：一遍过
思路：先计算短的链表的长度，再计算长的链表与其差值n，目的是使链表右端对齐。接着长的链表先走n个节点，两节点再携手共进，若两个指针所指的节点为同一个，则返回该该节点；否则返回空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int m=0,n1=0,n2=0;
        ListNode *p=headA,*q=headB;
        for(;p!=NULL&&q!=NULL;p=p->next,q=q->next,m++);
        while(p!=NULL){
            p=p->next;
            n1++;
        }
        while(q!=NULL){
            q=q->next;
            n2++;
        }
        p=headA;q=headB;
        while(n1--) p=p->next;
        while(n2--) q=q->next;
        while(q!=NULL){
            if(q==p){
                return q;
            }
            q=q->next;
            p=p->next;
        }
        return NULL;
       
    }
};

改进：看了答案的代码大为震撼
A长度为a,B长度为b，将两者末尾再接上对方的链表的头
A —- A+B
B —- B+A
原理都一样，若A短B长，当B走完自身长度时，A自身已经走完，且多走的距离正是B比A长的距离。这距离本应该在第二次遍历时，让B先走，因此A后接B相当于提前开启第二次遍历，当B走完时接着走A，这时的状态恰好是新一轮的B（A后的B）走了比A多的距离。在此之后携手一同向后走即可找到。
只能说牛犇，我还得练。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while (A != B) {
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};

142.环形链表II

题目链接
状态： 一遍过
思路：之前做过有印象，就是追问题，使用快慢指针。设表头到入口距离为x，相遇点距入口距离为a，环剩余距离为b。因为快慢指针速度为1：2，所以在慢指针进入入口后的第一圈内即可相遇，二者的走过的距离比也是1：2 =x+a:x+a+b+a，计算可得x=b，而环的长度为x+a。由此可知在相遇后从表头重新找个新指针，二者以相同的速度走，待下次相遇时所在的节点即为入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode *q = head, *p=head;
        while (p != NULL && p->next != NULL) {
            q = q->next;
            p = p->next->next;
            if (q == p) {
                p = head;
                while (q != p) {
                    q = q->next;
                    p = p->next;
                }
                return p;
            }
        }
        return NULL;
    }
};