LeetCode链表的几道基础题_leetcode几道题

本次所写的C++代码均已通过提交

本文所提到的一部分代码是参考别人所写的，对他们表示由衷的感谢。
题目号：2,19,21,23

第二道题 两数相加

// An highlighted block
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* pHead=new ListNode(0);//创建一个存放结果的链表
        ListNode *pCurrent=pHead;//链表移动的指针
        int overload=0;//是不是有进位；有进位为1；
        while(l1||l2||overload)
        {
            int sum=(l1?l1->val:0)+(l2?l2->val:0)+overload;//某一位的值为l1/l2的值加上进位的值；
            if(sum>=10)//如果这个和大于10
            {
                sum%=10;//更新这个值
                overload=1;//并且产生进位；
            }
            else
                overload=0;
            pCurrent->next=new ListNode(sum);//将当前的值赋给第一位；也就是个位数；
            pCurrent=pCurrent->next;//当前的位置往下进行；也就是十位数
            if(l1) l1=l1->next;//l1链表往后遍历；
            if(l2) l2=l2->next;//l2链表往后遍历；
        }
        return pHead->next;
    }
};
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

思路：
首先创建一个链表和对应的指针
创建一个进位标志位
While(l1||l2||overload)不可省去 overload 会造相同长度无法进位的问题。
计算个位
判断是否大于10 否则进位等于1
之后将 当前的值付给第一位 pcurrent=new ListNode（sum）
指针也随后进位到下一位pcurrent=pcureent->next;
随后将l1 l2 往后遍历。

删除链表倒数第n个节点

思路：用一个快慢指针 快指针比满指针快n 步 当快指针等于0的时候 slow-next=slow->next->next 具体解释可见部分题解。

// An highlighted block

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy= new ListNode(0);
        dummy->next=head;
        ListNode* pslow=head;
        ListNode* pfast=head;//声明快慢指针
        ListNode* pre=NULL;
        if(head->next==NULL&&n!=0) return NULL;
        while(--n)
            pfast=pfast->next;
        while(pfast->next!=NULL){
            pre=pslow;
            pfast=pfast->next;
            pslow=pslow->next;
        }
        if(pre!=NULL) pre->next=pslow->next;
        if(pslow==head)
            return head->next;
        pslow->next=NULL;
        return head;
        // pslow->next=pslow->next->next;//删掉倒数第二个
        // return dummy->next;

    }
};
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
35
36

有序链表相加

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
思路： 创建一个新的链表 从头开始对l1 l2链表的第一个节点比较(排除掉其他因素：链表为空) 取较小的放在新的链表中 此链表进一位，随后继续在两个链表进行比较直到链表都为空。

// An highlighted block
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head =new ListNode(0);
        ListNode* point =head;
        if(!l1&&!l2){
            return nullptr;
        }
        if(!l1){
            return l2;
        }
        if(!l2){
            return l1;
        }
        while(l1&&l2){
            if(l1->val<l2->val){
               head->next=l1;
               head=head->next;
               l1=l1->next;
            }
            else{
                head->next=l2;
                head=head->next;
                l2=l2->next;
            }
            //point=point->next;
        }
        if(l1 == NULL)
            head->next = l2;
        else
            head->next = l1;
        return point->next;
    }
};

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
35
36

延伸：k个有序链表组合成一个
思路就是先写一个类似上面的函数：然后下一个循环将所有的链表加起来。

在上面函数的基础上加上下面这个函数

// An highlighted block
ListNode* mergeKLists(vector<ListNode*>& lists) {
      int n=lists.size();
      int k=1;
      while(k<n){
              for (int i=0;i<n-k;i +=2*k){
                  lists[i] = merge2Lists(lists[i], lists[i + k]);
                 //k=1:0=0+1;2=2+3;4=4+5;   k=2:0=0+2 ;4   k=4:0=0+4;最后返回lists[0]
              }
              k*= 2;
      }
      if(n>0){
          return lists[0];
      }
      else{
          return nullptr;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16