🐳链表🐳

排序由易到难

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

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

解题思路

  • 使用快慢指针法，让快指针提前先走n+1步，再同步快慢指针直到快指针指向链表结尾时，慢指针刚好停留在需要删除结点的前驱。
  • 添加头结点 dummy 是为了统一对链表增删的操作。
  • 删除结点相当于链接时跳过此结点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy=new ListNode(-1);
        dummy->next=head;
        ListNode* fast=dummy;
        ListNode* slow=dummy；
        int cnt=n+1;
        while(cnt--){
            fast=fast->next;
        }
        while(fast){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return dummy->next;
    }

    合并两个有序链表

    Leetcode将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    解题思路

  • 合并为一个新的链表用尾插法，三个指针：l1，l2用于遍历两个链表，cur用于遍历新的链表
  • 涉及新建链表一般都需要new一个头结点和定义一个指针用于遍历。
  • 同时遍历两个链表，把比较小的结点用尾插法插入到新的链表中，再更新指针。
  • while结束标志为：其中一个链表遍历结束
  • 如果一个链表遍历结束，另一个未结束，则把未结束的剩余部分链接上
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head=new ListNode(-1);
        ListNode* cur=head;
        //尾插法
        while(l1 && l2){
            if(l1->val <= l2->val){
                cur->next=l1;
                l1=l1->next;
            }else{
                cur->next=l2;
                l2=l2->next;
            }
            cur=cur->next;
        }
        if(!l1) cur->next=l2;
        if(!l2) cur->next=l1;
        return head->next;
    }

    两两交换链表中的节点

    Leetcode给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
    你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

    示例

    1
    给定 1->2->3->4, 你应该返回 2->1->4->3.

    解题思路

  • 使用头节点，用于链表第一结点与其他结点增删改的统一。
  • 定义三个指针，cur用于遍历原链表，p1,p2用于交换（p2指向p1的后继结点）
  • 链接的顺序：1->3 2->1 cur->2
  • 注意：cur指针每次向前跳两步。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
     ListNode* swapPairs(ListNode* head) {
        ListNode* dummy=new ListNode(-1);
        dummy->next=head;
        ListNode* cur=dummy;
        ListNode* p1=dummy;
        ListNode* p2=dummy;
        while(cur->next && cur->next->next){
            p1=cur->next;
            p2=cur->next->next;
            p1->next=p2->next;
            p2->next=p1;
            cur->next=p2;
            cur=cur->next->next;
        }
        return dummy->next;
    }

删除排序链表中的重复元素

Leetcode给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

解题思路

  • 链表中删除一个结点相当于指针越过该结点（next指针指向要删除结点的后继）
  • 直到cur与下一个结点值不同时，更新指针
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
       ListNode* deleteDuplicates(ListNode* head) {
           ListNode* cur=head;
           while(cur && cur->next){
               if(cur->val == cur->next->val) 
    cur->next=cur->next->next;
               else 
    cur=cur->next; 
           }
           return head;
       }

环形链表

leetcode给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

解题思路

  • 当快指针检查到无下一节点时，说明该链表无环，当链表中不存在环时，快指针终将优先到达链表尾部。
  • 当快指针与慢指针相遇（指向同一个节点）时，说明该链表有环。快指针追上慢指针了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    bool hasCycle(ListNode *head) {
        if (head == NULL) return false;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }

相交链表

leetcode编写一个程序，找到两个单链表相交的起始节点。

解题思路

  • 分别遍历一条链表，当遍历到结尾时让指针指向另一条链表的头部继续遍历另一条，当两个指针相等时即相交的位置
  • 原理：加入两条链表相交，链表1为A+C,链表2为B+C， C为两条链表相交以后的公共部分，此时指针p1遍历的长度为A+C+B,指针p2遍历长度为B+C+A,两指针刚好落在相交部分的开头，因为如果继续遍历的话，两个指针都将同时遍历C部分。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL && headB == NULL) return NULL;
        if (headA == NULL || headB == NULL) return NULL;
        ListNode* p1 = headA;
        ListNode* p2 = headB;
        while(p1 != p2) {
            p1 = p1 == NULL ? headB : p1->next;
            p2 = p2 == NULL ? headA : p2->next;
        }
        return p1;
    }

反转链表

Leetcode 反转一个单链表。

解题思路

  • 链表的头插法实现反转，需要两个指针，当前指针cur,新链表头部指针pre
  • 因为需要改变当前结点next指针指向pre，所以必须先记录下next指针最后再恢复，才能让cur继续在链中遍历下去。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        while (cur) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    回文链表

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

    解题思路

  • 用快慢指针法先找到中间结点，用头插法反转后一半链表，用双指针比较两个链表。
  • 快慢指针注意while的结束条件：
    • 如果while(fast && fast->next)则奇数链表慢指针指向中间结点，偶数链表慢指针指向后一半链表头部。
    • 如果while(fast->next && fast->next->next则不论奇数偶数链表，慢指针都指向后一半链表的前一个结点。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      bool isPalindrome(ListNode* head) {
          if (head == NULL || head->next == NULL) return true;
          ListNode * slow = head;
          ListNode * fast = head;
          while (fast->next && fast->next->next) {
              slow = slow->next;
              fast = fast->next->next;
          }
          ListNode* cur = slow->next;
          ListNode* pre = NULL;
          while (cur) {
              ListNode* tmp = cur->next;
              cur->next = pre;
              pre = cur;
              cur = tmp;
          }
          while (pre && head) {
              if(pre->val != head->val) return false;
              pre = pre->next;
              head =head->next;
          } 
          return true;
      }

奇偶链表

leetcode给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

解题思路

  • 需要两个指针，一个指向奇数结点，一个指向偶数结点，分别往后跳跃遍历
  • 注意while循环的结束条件，因为两个指针都是跳跃一步的往后遍历，所以只有指针的下一步不是NULL时才能跳跃。
  • 注意提前保存偶数链表的头部，用于之后的拼接。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    ListNode* oddEvenList(ListNode* head) {
         if (head == NULL) return NULL;
         ListNode* odd = head;
         ListNode* even = head->next;
         ListNode* preEven = even;
         while (odd->next && even->next) {
             odd->next = odd->next->next;
             odd = odd->next;
             even->next = even->next->next;
             even = even->next;
         }
         odd->next = preEven;
         return head;
     }

两数相加II

leetcode给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

解题思路

  • 题意，不能反转链表，那么对于这种逆序操作第一要想到用栈。
  • 本体使用了三种技巧：1、使用栈逆序储存，2、两数相加（涉及到进位carry的操作），3、头插法建立链表.
  • 注意：当某一个位没有数时（即栈为空时）用0代替，进行相加。
    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
    29
    30
    31
    32
    33
    34
     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> sck1, sck2;
        while (l1) {
            sck1.push(l1->val);
            l1 = l1->next;
        }
        while (l2) {
            sck2.push(l2->val);
            l2 = l2->next;
        }
        int a = 0, b = 0, carry = 0;
        ListNode* pre = NULL;
        while (!sck1.empty() || !sck2.empty() || carry) {
            if (!sck1.empty()) {
                a = sck1.top();
                sck1.pop();
            } else {
                a = 0;
            }
            if (!sck2.empty()) {
                b = sck2.top();
                sck2.pop();
            } else {
                b = 0;
            }
            int sum = a + b + carry;
            carry = sum / 10;
            sum %= 10;
            ListNode* newNode = new ListNode(sum);
            newNode->next = pre;
            pre = newNode;
        }
        return pre;
    }

分隔链表

leetcode给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。
这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。

示例

1
2
3
4
5
6
7
输入: 
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]

输入: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

解题思路

  • 本体涉及的技巧有：计算链表长度，计算每段的长度，分割并储存链表(定位尾部，保存头部)
  • 首先计算链表总长度，根据k值求出每段的平均长度，由题意任意两部分的长度差距不能超过 1，且较长的在前面，所以将余的部分平均分给前面的链表长度上面。
  • 得到每一段的长度后，开始分割链表，链表的分割只需要遍历到尾结点，在尾节点后加NULL即可，而储存链表时只需要储存链表头结点即可。
  • 注意：已知链表长度，通过while(--len > 0）来定位链表尾部时，while里面要先自减。
  • 注意：在尾结点后加NULL分割链表之前，防止下一步丢失，要事先保存下一步的结点，以便更新当前结点。
    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
    29
    30
     vector<ListNode*> splitListToParts(ListNode* root, int k) {
        int len = 0;
        ListNode* cur = root;
        while (cur) {
            len++;
            cur = cur->next;
        }
        int averageLen = len / k;
        int surplusLen = len % k;
        int curLen = 0;
        cur = root;
        vector<ListNode*> res;
        for (int i = 0; i < k; ++i) {
            res.push_back(cur);
            if (surplusLen-- > 0) {
                curLen = averageLen + 1;
            } else {
                curLen = averageLen;
            }
            while (--curLen > 0 ){
                cur = cur->next;   
            }
            if (cur != NULL) {
                ListNode* tmp = cur->next;
                cur->next = NULL;
                cur = tmp;
            }   
        }
        return res;
    }

链表组件

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

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释: 
链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。

输入: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
输出: 2
解释: 
链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。

解题思路

  • 首先为G列表的值建立一个bool类数组，（也可以使用哈希表，但是效率太低）用于遍历链表时检查结点是否属于G列表中的结点。
  • 一遍遍历整个链表，当遇到第一个属于G列表中的结点时，组件数量就加1，并继续往后遍历找到组件的结尾，非G列表中的结点直接忽略即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    bool isIn[10000];
    int numComponents(ListNode* head, vector<int>& G) {
        if (head == NULL) return 0;
        for (auto it : G) {
            isIn[it] = true;
        }
        ListNode* cur = head;
        int cnt = 0;
        while (cur != NULL) {
            if (isIn[cur->val] == true) {
                while(cur != NULL && isIn[cur->val] == true) 
                    cur = cur->next;
                cnt++;
            } else {
                cur = cur->next;
            } 
        }
        return cnt;
    }