LeetCode 题解（3）：链表

learn from cyc2018 and LeetCode

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

160. Intersection of Two Linked Lists (easy)

问题描述

寻找两个单链表相交的起始位置。

如上图，$A$，$B$两个单链表相交起始于 $c_1$ 结点。

请控制时间复杂度在 $O(n)$，空间复杂度在 $O(1)$。

题解

设 $A$ 的长度为 $a+c$，其中 $a$ 是与链表 $B$ 不相交的部分。同理，设 $B$ 的长度为 $b+c$。那么要想使两个指针同时访问到交点：

$(a+c)+ b = (b+c)+a$
当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p = headA;
        ListNode *q = headB;
        while(p != q){
            if(p == NULL)
                p = headB;
            else
                p = p->next;
            if(q == NULL)
                q = headA;
            else
                q = q->next;
        }
        return p;
    }
};

206. Reverse Linked List (easy)

问题描述

翻转单链表。

题解

用递归的方法来做：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return p;
    }
};

这样做时间复杂度很低，但是空间使用很高。如果利用头插法，可以保持时间复杂度基本不变的情况下，显著提高空间效率。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode newNode(0);
        ListNode *p = &newNode;
        while(head != NULL){
            ListNode *q = head->next;
            head->next = p->next;
            p->next = head;
            head = q;
        }
        return p->next;
    }
};

21. Merge Two Sorted Lists (easy)

问题描述

归并两个有序列表

1
2
3

// example
// input: 1->2->4, 1->3->4
// output: 1->1->2->3->4->4

题解

对于单链表问题，首先考虑递归：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL)
            return l2;
        if(l2 == NULL)
            return l1;
        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

83. Remove Duplicates from Sorted List

问题描述

删除有序列表中的重复元素。

题解

考虑遍历整个列表

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

但是得到的结果却运行时间过长。

考虑用递归的方式求解：

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        head->next = deleteDuplicates(head->next);
        return head->val == head->next->val ? head->next : head;
    }
};

速度方面好于遍历整个列表的方式。

19. Remove Nth Node From End of List (medium)

问题描述

删除链表中倒数第 $n$ 个元素。

题解

利用双指针法求解。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* p = head;
        while(p != NULL && n > 0){
            p = p->next;
            -- n;
        }
        if(p == NULL) return head->next;
        ListNode* q = head;
        while(p->next != NULL){
            p = p->next;
            q = q->next;
        }
        q->next = q->next->next;
        return head;
    }
};

24. Swap Nodes in Pairs (medium)

问题描述

交换单链表中相邻两个元素的位置（不允许修改值）。

1 2	// example // Given 1->2->3->4, you should return the list as 2->1->4->3.

题解

递归。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode* q = head->next;
        head->next = swapPairs(head->next->next);
        q->next = head;
        return q;
    }
};

445. Add Two Numbers II (medium)

问题描述

给定两个用链表表示的大整数，链表首位表示最高位，链表末尾表示最低位。计算两个大整数的和。

注意：不能修改原始链表，即不允许进行链表翻转。

1
2
3

// example
// Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
// Output: 7 -> 8 -> 0 -> 7

题解

利用栈存储链表中数据即可。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1 = buildStack(l1);
        stack<int> s2 = buildStack(l2);
        int c = 0;
        ListNode* h = new ListNode(0);
        while(!s1.empty() || !s2.empty() || c != 0){
            int x = 0;
            int y = 0;
            if(!s1.empty()){
                x = s1.top();
                s1.pop();
            }
            if(!s2.empty()){
                y = s2.top();
                s2.pop();
            }
            int sum = x + y + c;
            c = sum / 10;
            ListNode *r = new ListNode(sum%10);
            r->next = h->next;
            h->next = r; 
        }
        return h->next;
    }
private:
    stack<int> buildStack(ListNode* l){
        stack<int> s;
        while(l != NULL){
            s.push(l->val);
            l = l->next;
        }
        return s;
    }
};

234. Palindrome Linked List (easy)

问题描述

判断单链表是否回文。注意，使用 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度。

题解

将链表从中间截开，翻转第二段链表，判断两段链表是否相等。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == NULL || head->next == NULL) return true;
        ListNode* fast = head->next;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* h2 = slow->next;
        slow->next = NULL;
        return isEqual(head, reverse(h2));
        
    }
private:
    ListNode* reverse(ListNode* head){
        ListNode *p = new ListNode(0);
        while(head != NULL){
            ListNode *q = head->next;
            head->next = p->next;
            p->next = head;
            head = q;
        }
        return p->next;
    }
    bool isEqual(ListNode* h1, ListNode* h2){
        while(h2 != NULL){
            if(h1->val != h2->val)
                return false;
            h2 = h2->next;
            h1 = h1->next;
        }
        return true;
    }
};

725. Split Linked List in Parts

问题描述

将给定单链表划分为 $k$ 组，每组元素数量尽可能相等，并且前一组数量一定大于等于后一组数量。

1
2
3

// example
// Input: root = [1, 2, 3], k = 5
// Output: [[1],[2],[3],[],[]]

题解

求出每组元素的个数，满元素组的数量与非满元素组的数量。

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        int c = 0;
        ListNode* p = root;
        vector<ListNode*> result;
        while(p != NULL){
            ++ c;
            p = p->next;
        }
        int npc = c / k + 1;        // number per class
        int fcn = c - c / k * k;     // fully class number
        int ncn = k - fcn;
        p = root;
        for(; fcn > 0; -- fcn){
            ListNode* head = new ListNode(0);
            ListNode* tail = head;
            for(int i = 0; i < npc; ++ i){
                ListNode* q = new ListNode(p->val);
                p = p->next;
                tail->next = q;
                tail = tail->next;
            }
            result.push_back(head->next);
        }
        for(; ncn > 0; -- ncn){
            ListNode* head = new ListNode(0);
            ListNode* tail = head;
            for(int i = 0; i < npc-1; ++ i){
                if(p == NULL)
                    break;
                ListNode* q = new ListNode(p->val);
                p = p->next;
                tail->next = q;
                tail = tail->next;
            }
            result.push_back(head->next);
        }
        return result;
    }
};

问题描述

给定一个单链表，将其所有偶数位元素链接，所有奇数位连接，并将所有偶数位连接的结果置于奇数位链接结果之后。

1
2
3

// example
// Input: 1->2->3->4->5->NULL
// Output: 1->3->5->2->4->NULL

题解

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == NULL) 
            return head;
        ListNode* h2 = head->next;
        ListNode* p = head;
        ListNode* q = h2;
        while(p != NULL && q != NULL && q->next != NULL){
            p->next = q->next;
            p = p->next;
            q->next = p->next;
            q = q->next;
        }
        p->next = h2;
        return head;
    }
};

LeetCode 题解（3）：链表

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

相关问题

问题描述

题解

相关问题