力扣24：两辆交换链表中节点

题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

解题思路

• 思路上相对比较简单；需要注意的是代码实现的操作过程中，注意丢失节点，不要导致访问不到。核心要点是：链表是链式存储，头节点是访问链表的唯一入口，上一个节点是访问下一个节点的必要入口。

• 其二就是在判断终止的边界条件时，如果想不好怎么写边界条件，可以进行举例，如果是空怎么办，如果只有一个节点怎么办，如果只有两点节点怎么办。

  完整代码

  /**
   * 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* swapPairs(ListNode* head) {
          ListNode *dummyHead = new ListNode(0);  //新建虚拟头节点
          dummyHead->next = head;      //将虚拟头节点放在头节点前面
          ListNode *cur = dummyHead;   //定义用来实际操作的节点，防止丢失头节点
  
          //开始遍历交换操作
          while(cur->next != nullptr && cur->next->next != nullptr){
               ListNode *tmp = cur->next;   //保存头节点
               ListNode *tmp1 = cur->next->next->next;  //保存第三个节点
               cur->next = cur->next->next;   //下面开始操作
               cur->next->next = tmp;
               cur->next->next->next = tmp1;
               cur = cur->next->next;
          }
          return dummyHead->next;
      }
  };

力扣19：删除链表中倒数第N个节点

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解题思路

• 最初未看题解的时候考虑的是：目标是将cur移动到待删除节点的前一个节点；具体实现思路是先通过while循环计算链表的长度，然后使用链表的长度和n的值来移动cur节点。
• 但是看了快慢指针之后，发现使用快慢指针的解法更加优雅。核心思想是先将快指针向前移动n+1步，之后再将快指针和慢指针同步移动。这种思路就不用管链表的长度了，优雅！

完整代码

第一种思路解法：

/**
 * 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 *dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode *cur = dummyHead;
        ListNode *cur1 = dummyHead;
        int size = 0;    //初始化链表长度
        //求解链表长度
        while(cur1->next != nullptr){
            size++;
            cur1 = cur1->next;
        }

        //移动cur节点到待删除的节点的前一个
        int num = size - n;
        while(num){
            ListNode *tmp = cur->next;
            cur = cur->next;
            num--;
        }

        //进行删除处理
        ListNode *tmp1 = cur->next;
        cur->next = cur->next->next;
        delete tmp1;
        return dummyHead->next;
    }

};

双指针解法代码实现，如果有不明确的地方，在纸上勾勾画画就知道了。在写代码时，除非自己对这个流程很熟悉，不然就先在纸上把伪代码写好，整理好自己的逻辑，再落实为具体的代码。

/**

 * 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 *dummpHead = new ListNode(0);
        dummpHead->next = head;
        ListNode *fast = dummpHead;
        ListNode *slow = dummpHead;
        n ++;

          //先移动fast指针
        while(n-- && fast != nullptr){
            fast = fast->next;
        }

        //同时移动快指针和慢指针
        while(fast != nullptr){
            slow = slow->next;
            fast = fast->next;
        }

        //删除指定节点
        ListNode *tmp = slow->next;
        slow->next = slow->next->next;
        delete tmp;
        return dummpHead->next;
    }
};

力扣02.07: 链表相交

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

解题思路

这题重点要理解：当链表相等时，后面的链表值也必定相等；所以核心思路是：将两个链表尾对其，对其之后从开始对其的节点进行比较，判断是否相等，如果是则返回该节点，如果不是则返回空。

• 计算两个链表长度
• 尾对其两个链表（移动较长的那个链表）

• 进行比较，判断是否符合条件，并作出响应。

  完整代码

  /**
   * 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 *curA = headA;
          ListNode *curB = headB;
          int sizeA = 0;
          int sizeB = 0;
  
          //统计链表长度
          while(curA != NULL){
              curA = curA->next;
              sizeA++;
          }
          while(curB != NULL){
              curB = curB->next;
              sizeB++;
          }
  
          //要注意还原curA和curB链表
          curA = headA;
          curB = headB;
  
          //确保sizeA的值是最大的
          if(sizeA < sizeB){
              swap (sizeA, sizeB);
              swap (curA, curB);
          }
  
          //开始尾对其两个链表
          int gap = sizeA - sizeB;
          while(gap--){
              curA = curA->next;
          }
  
          //开始进行比较
          while(curA != NULL){
              if(curA == curB){
                  return curA;
              }
              curA = curA->next;
              curB = curB->next;
          }
          return NULL;
      }
  };

力扣142: 环形链表

题目描述

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 _如果链表无环，则返回 null。_

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

解题思路

使用快慢指针来解决问题。
核心问题有两个：
第一：找到快慢指针相遇的位置。
第二：找到进入循环的位置。

完整代码

/**

 * 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 *fast = head;
        ListNode *slow = head;
        while(fast != NULL && fast->next != NULL){
            fast = fast->next->next;
            slow = slow ->next;
            if(fast == slow){
                ListNode *index1 = fast;
                ListNode *index2 = head;
                while(index1 != index2){
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return NULL;
    }
};

今日小结

日渐消瘦、日渐熟练这种思维模式。