Leetcode 刷题笔记-Leetcode 101 第13章 链表

Leetcode 刷题笔记-Leetcode 101 第13章 链表

链表

（单）链表是由节点和指针构成的数据结构，每个节点存有一个值，和一个指向下一个节点的指针，因此很多链表问题可以用递归来处理。不同于数组，链表并不能直接获取任意节点的值，必须要通过指针找到该节点后才能获取其值。同理，在未遍历到链表结尾时，我们也无法知道链表的长度，除非依赖其他数据结构储存长度。

链表的基本操作

Leetcode 206

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* p = nullptr;
        ListNode* q = head;
        while(q){
            ListNode* r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        return p;
    }
};

分析：两种方式，迭代法和递归法反转链表。

错误：算法忘记了，稍稍看了一眼后明白了

Leetcode 21

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

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* result = new ListNode(-1);
        ListNode* head = result;
        while(list1 != nullptr && list2 != nullptr){
            if(list1->val > list2->val){              
                head->next = list2;
                list2 = list2->next;
            }
            else{
                head->next = list1;
                list1 = list1->next;
            }
            head = head->next;
        }
        if(list1 != nullptr){
            head->next = list1;
        }
        else{
            head->next = list2;
        }
        return result->next;
    }
};

分析：按照顺序一点一点合并即可，前面设置一个头结点，后面把它扔掉返回。

错误：链表操作忘记了

Leetcode 24

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

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* pre = new ListNode(-1);
        pre->next = head;
        head = pre;
        while(pre->next != nullptr && pre->next->next != nullptr){
            ListNode* p = pre->next;
            ListNode* q = p->next;
            pre->next = q;
            p->next = q->next;
            q->next = p;
            pre = p;
        }
        return head->next;
    }
};

分析：链表操作

错误：已经不熟练了，不知道什么时候加结点什么的。

其它链表技巧

Leetcode 160

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

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == nullptr || headB == nullptr){
            return nullptr;
        }
        ListNode* pa = headA;
        ListNode* pb = headB;
        while(pa != pb){
            if(pa == nullptr){
                pa = headB;
                pb = pb->next;
            }
            else if(pb == nullptr){
                pb = headA;
                pa = pa->next;
            }
            else{
                pa = pa->next;
                pb = pb->next;
            }
        }
        return pa;
    }
};

分析：当链表headA和headB都不为空时，创建两个指针pA和pB，初始时分别指向两个链表的头节点headA和headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：每步操作需要同时更新指针pA和pB。如果指针pA不为空，则将指针pA移到下一个节点；如果指针 pB不为空，则将指针pB移到下一个节点。如果指针pA为空，则将指针pA移到链表headB的头节点；如果指针pB为空，则将指针pB移到链表headA的头节点。当指针pA和pB指向同一个节点或者都为空时，返回它们指向的节点或者null。

错误：不会做

Leetcode 234

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vt;
        while(head != nullptr){
            vt.push_back(head->val);
            head = head->next;
        }
        int n = vt.size();
        for(int i=0;i<n/2;++i){
            if(vt[i] != vt[n-i-1]){
                return false;
            }
        }
        return true;
    }
};

分析：复制到数组中判断

一遍AC

练习

Leetcode 83

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* p = head;
        if(p == nullptr){
            return nullptr;
        }
        while(p->next != nullptr){
            ListNode* q = p->next;
            if(p->val == q->val){
                p->next = q->next;
                q = p->next;
            }
            else{
                q = q->next;
                p = p->next;
            }
        }
        return head;
    }
};

分析：遍历判断即可

错误：没有考虑链表中没有结点的情况。

Leetcode 328

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == nullptr){
            return head;
        }
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenhead = even;
        while(even != nullptr && even->next != nullptr){
            odd->next = even->next;
            even->next = even->next->next;
            odd = odd->next;
            even = even->next;
        }
        odd->next = evenhead;
        return head;
    }
};

分析：单独存储奇偶结点即可。

错误：还是不熟练

Leetcode 19

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

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* p = head;
        int sum = 0;
        while(p != nullptr){
            ++sum;
            p = p->next;
        }
        p = head;
        int num = sum - n;
        if(num == 0){
            return head->next;
        }
        ListNode* pre = new ListNode(-1);
        pre->next = p;
        for(int i=0;i<num;++i){
            pre = p;
            p = p->next;
        }
        pre->next = p->next;
        return head;
    }
};

分析：先数一遍一共有多少个结点，然后再遍历一遍删掉即可。

一遍AC

Leetcode 148

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == nullptr){
            return head;
        }
        vector<int> result;
        ListNode* p = head;
        while(head != nullptr){
            result.push_back(head->val);
            head = head->next;
        }
        sort(result.begin(),result.end());
        head = p;
        int index = 0;
        while(head != nullptr){
            head->val = result[index++];
            head = head->next;
        }
        return p;
    }
};

分析：可以用一些比较高大上的链表排序方法，也可以耍赖，直接读入数组中排序即可。

一遍AC

总结

链表不难，就是太容易忘记了，后面要经常复习。