力扣刷题记录-链表/c++_力扣 链表 c++

题库21题：合并两个有序链表(简单）

题目描述

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

解法

思路：
若有空链表，则直接返回另一个链表
两个链表都不为空开始比较，哪个链表的值小，哪个就将tail指向哪个链表，并且该链表指针向后移
当某链表已经到达最后一个元素时，证明该链表的最大值也小于另一链表当前的值，tail直接指向另一链表当前位置

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head = nullptr;
        ListNode *tail = nullptr;
        //若有空链表，则返回另一个链表
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        //两个链表都不为空开始比较
        //哪个链表的值小，哪个就将tail指向哪个链表，并且该链表指针向后移
       while(l1 != NULL && l2 != NULL){
           if(l1->val <= l2->val)
           {
               if(!head)
               {
                   head = tail = new ListNode(l1->val);
                   l1 = l1->next;
               }
               else
               {
                   tail->next = new ListNode(l1->val);
                   tail = tail->next;
                   l1 = l1->next;
               }
           } 
           else
           {
               if(!head)
               {
                   head = tail = new ListNode(l2->val);
                   l2 = l2->next;
               }
               else
               {
                   tail->next = new ListNode(l2->val);
                   tail = tail->next;
                   l2 = l2->next;
               }
           }
       }
       //当某链表已经到达最后一个元素时，证明该链表的最大值也小于另一链表的值，tail直接指向另一链表当前位置
    tail->next = (l1 ? l1:l2) ;
    return head;
    }
};
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
37
38
39
40
41
42
43
44
45
46
47

运行结果

题库24题：两两交换链表中的节点（中等）

题目描述

思路

解法

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* temp = dummyhead;
        while(temp->next != nullptr && temp->next->next != nullptr)
        {   
            ListNode* n1 = temp->next;
            ListNode* n2 = temp->next->next;
            temp->next = n2;
            n1->next = n2->next;
            n2->next = n1;
            temp = n1;
        }
        return dummyhead->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题库61题：旋转链表（中等）

题目描述

思路

计算链表长度并找到尾节点
计算出新head位置，指针指向新head的前一个节点
前一个节点作为新的尾节点，指向null，head指向新head

解法

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
    	//链表为空或只有一个元素，直接返回
        if(!head || !head->next)
            return head;
        int n = 1;
        ListNode* p = head;
        ListNode* q = head;
        //找到尾节点并计算链表长度
        while(p->next)
        {
             p = p->next;
            n++;
        }
        //计算循环的实际 次数
        k = k%n;
        if(!k)
            return head;
        p->next = head;
        for(int i = 0;i < n - k - 1;i++)
           q = q->next;
        head = q->next;
        q->next = NULL;
        return head;
    }
};
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

运行结果

题库83题：删除列表中的重复元素（简单）

题目描述

思路

建立哑节点指向头节点
cur指针不断后移，如果和head指向的节点相同就一直后移，若不同则head和cur均后移

解法

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* cur = head;
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        if(!head || !head->next)
            return head;
        while(cur)
        {
            if(cur->next && cur->val == cur->next->val)
            {
                while(cur->next && cur->val == cur->next->val)
                    cur = cur->next; 
                cur = cur->next;    
                head->next = cur;
                head = head->next;
            } 
            else if(cur->next && cur->val != cur->next->val)
            {
                cur = cur->next;
                head->next = cur;
                head = head->next;
            }
            else
                return dummyhead->next;
        }
        return dummyhead->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

运行结果