链表问题（二）-LeetCode 147、876、234、817、92（链表的中点，快慢指针）

• 2019 年 12 月 13 日
• 筆記

1

编程题

【LeetCode #147】对链表进行插入排序

对链表进行插入排序。

示例 1： 输入: 4->2->1->3 输出: 1->2->3->4

解题思路：

首先判断两个相邻节点的大小，如果head->val > head->next->val，则需要将head->next->val插入到从dummy节点开始遍历第一个大于head->next->val节点的前面！好好理解这句话！在进行插入的时候，首先使用cur指针标记head->next节点，并改变head->next的指向。从而将待插入节点分离！接着就是普通的插入操作了！

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      ListNode* insertionSortList(ListNode* head) {          if(head == nullptr || head->next == nullptr) return head;          ListNode* dummy = new ListNode(), *pre = nullptr;          dummy->next = head;          while(head->next != nullptr){              if(head->val <= head->next->val){  // 无需进行插入操作                  head = head->next;                  continue;              }              pre = dummy;              while(pre->next->val < head->next->val){                  pre = pre->next;              }              ListNode* cur = head->next;              head->next = cur->next;              cur->next = pre->next;              pre->next = cur;          }          return dummy->next;      }  };  

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/insertion-sort-list/

【LeetCode #876】链表的中间结点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。

示例 1： 输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。(测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

解题思路：快慢指针，注意与下一题中的回文链表的中间结点进行区别！

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      ListNode* middleNode(ListNode* head) {          if(head == nullptr || head->next == nullptr) return head;          ListNode* slow = head, *fast = head;          while(fast != nullptr && fast->next != nullptr){              slow = slow->next;              fast = fast->next->next;          }          return slow;      }  };  

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/middle-of-the-linked-list

【LeetCode #234】回文链表

请判断一个链表是否为回文链表。

示例 1: 输入: 1->2 输出: false

解题思路：

找到中点（奇数时不是真正的中点，注意与上题区别），然后反转后面的链表，再进行节点值得比较即可！

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      bool isPalindrome(ListNode* head) {          ListNode* slow = head, *fast = head, *pre = nullptr;          while(fast != nullptr){              slow = slow->next;              fast = fast->next ? fast->next->next : nullptr;          }   // 这里的中点偶数时为第二个节点，奇数时为中点的下一个节点！          while(slow != nullptr){              ListNode* next = slow->next;              slow->next = pre;              pre = slow;              slow = next;          }          while(pre && head){              if(pre->val != head->val){                  return false;              }              pre = pre->next;              head = head->next;          }          return true;      }  };  

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/middle-of-the-linked-list

【LeetCode #817】链表组件

给定一个链表（链表结点包含一个整型值）的头结点 head。 同时给定列表 G，该列表是上述链表中整型值的一个子集。 返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。

示例 1： 输入: head: 0->1->2->3 G = [0, 1, 3] 输出: 2 解释: 链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。

解题思路：

一开始题目没有看太懂，可能语文不太好！他的意思就是，如果连续相邻的链表节点值都在G这个数组中，那么这为一个组件，如果不在，则忽略！最终答案是G中有多少个组件。 比如0->1->3->2, 而G = [1,3,0] 则答案为 1。 我们查询可以在set中进行，设置布尔变量flag的作用是：用true标记这是一个组件，而false表示组件断开了，此时res++, 但有可能我们遍历的节点一直都不在G中。因此res++需要一个条件限制，即flag = true.

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      int numComponents(ListNode* head, vector<int>& G) {          set<int> s(G.begin(), G.end());          int res = ;          bool flag = false;   // 找到标记为true          while(head != nullptr){              auto it = s.find(head->val);              if(it != s.end()){   // 找到了                  flag = true;              }else{               // 没找到，前面的作为一个组件                  if(flag){ res++; }                  flag = false;              }              head = head->next;          }          if(flag) res++;          return res;      }  };  

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-components

【LeetCode #92】反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      ListNode* reverseBetween(ListNode* head, int m, int n) {          ListNode* dummy = new ListNode();          dummy->next = head;          ListNode* pre = dummy;          for(int i = ; i < m; i++){              pre = pre->next;          }          head = pre->next;          for(int i = m; i < n; i++){              ListNode* tmp = head->next;              head->next = tmp->next;              tmp->next = pre->next;              pre->next = tmp;          }          return dummy->next;      }  };  

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list-i