【算法】【链表】链表相关问题总结

2021-01-14 15:14

阅读：735

标签：双向数据结构 solution roo 业务逻辑 strong content intersect res

剑指offer

6. 从尾到头打印链表

题目链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector reversePrint(ListNode* head) {
        if(!head)
            return {};
        vector v = reversePrint(head->next);
        v.push_back(head->val);
        return v;
    }
};

栈

class Solution {
public:
    vector reversePrint(ListNode* head) {
        vector v;
        ListNode* cur = head;
        while (cur) {
            v.push_back(cur->val);
            cur = cur->next;
        }
        reverse(v.begin(), v.end());
        return v;
    }
};

reverse数组

class Solution {
public:
    vector reversePrint(ListNode* head) {
        vector v;
        ListNode* cur = head;
        while (cur) {
            v.push_back(cur->val);
            cur = cur->next;
        }
        reverse(v.begin(), v.end());
        return v;
    }
};

18. 删除链表的节点

题目链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        auto dummy = new ListNode(-1);
        dummy -> next = head;
        auto tmp = dummy;
        while(head && head -> val != val)
        {
            tmp = tmp -> next;
            head = head -> next;
        }
        // cout  val  val  next = head -> next;
        return dummy -> next;
    }
};

22. 链表中倒数第k个节点

题目链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

快慢指针

快指针比慢指针快k个节点，当快指针指向尾结点的下一个节点的时候，慢指针指向倒数第k个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* fast = head;
        ListNode* low = head;
        while(fast){
            fast = fast -> next;
            if(k > 0) k--;
            else low = low -> next;
        }
        return low;
    }
};

24. 反转链表

题目链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

思路

依次遍历链表，遍历一个逆置一个。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *new_head = nullptr;
        while(head)
        {
            ListNode *next = head->next;
            head->next = new_head;
            new_head = head;
            head = next;
        }
        return new_head;
    }
};

25. 合并两个排序的链表

题目链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

使用一个

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* new_head = new ListNode(-1); //保存合并后的头结点
        ListNode* tmp = new_head; //遍历链表
        while(l1 && l2)
        {
            //小的追加到tmp后面
            if(l1 -> val  val)
            {
                tmp -> next = l1;
                l1 = l1 -> next;
            }
            else
            {
                tmp -> next = l2;
                l2 = l2 -> next;
            }
            //更新tmp
            tmp = tmp -> next;
        }
        //没处理完的直接追加到后面
        tmp -> next = l1 ? l1 : l2;
        return new_head -> next;
    }
};

35. 复杂链表的复制

题目链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/

哈希

用哈希表做一个映射，hashmap的key是原先的节点，val是复制的节点。先初始化hashmap，然后分别next指针和random指针。

哈希表的作用：找到每个点的对应点（复制点）

时间复杂度O(n) 空间复杂度O(n)

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return head;

        unordered_map hashmap;
        hashmap[NULL] = NULL;
        //初始化hashmap
        //hashmap key是原先的节点p val是新节点
        for(auto p = head; p; p = p -> next)
            hashmap[p] = new Node(p -> val);

        for(auto p = head; p; p = p -> next)
        {
            //复制next指针
            hashmap[p] -> next = hashmap[p -> next];
            //复制random指针
            hashmap[p] -> random = hashmap[p -> random];
        }
        return hashmap[head];
    }
};

迭代

先复制正常的next节点，不复制random节点。之后复制指针的指向

时间复杂度O(n) 空间复杂度O(1)

*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        //在每个节点后面添加它的复制
        //复制next节点 复制的节点保存在原先节点的next指针处
        //新复制的节点的next指针的原先节点的next指针
        //原先： 1->2->3->4->5->null
        //now： 1->1->2->2->3->3->4->4->5->5->null
        for(auto p = head; p;)
        {
            auto np = new Node(p -> val);
            auto next = p -> next;
            p -> next = np;
            np -> next = next;
            p = next;
        }
		//复制random指针
        for(auto p = head; p; p = p -> next -> next)
            if(p -> random)
                p -> next -> random = p -> random -> next;
        //原链表不能修改 还原
        //遍历链表 分开两个链表
        auto dummy = new Node(-1);
        auto cur = dummy;
        for(auto p = head; p; p = p -> next)
        {
            cur -> next = p -> next;
            cur = cur -> next;
            p -> next = p -> next -> next;
        }
        return dummy -> next;
    }
};

36. 二叉搜索树与双向链表

题目链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

递归

Leetcode要求改成双向循环链表

剑指offer是改成双向链表

题目链接：https://www.acwing.com/problem/content/87/

left 改成前驱

right 改成后继

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* convert(TreeNode* root) {
        if (!root) return NULL;
        auto sides = dfs(root);
        return sides.first;
    }

    pair dfs(TreeNode* root)
    {
        //叶子节点
        if (!root->left && !root->right) return {root, root};
        //左右子树都有
        if (root->left && root->right)
        {
            //递归处理左右子树
            auto lside = dfs(root->left), rside = dfs(root->right);
            //拼接左右子树
            lside.second->right = root, root->left = lside.second;
            root->right = rside.first, rside.first->left = root;
            return {lside.first, rside.second};
        }
        //只有左子树
        if (root->left)
        {
            auto lside = dfs(root->left);
            lside.second->right = root, root->left = lside.second;
            return {lside.first, root};
        }
        //只有右子树
        if (root->right)
        {
            auto rside = dfs(root->right);
            rside.first->left = root, root->right = rside.first;
            return {root, rside.second};
        }
    }
};

Leetcode

92. 反转链表II

题目链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/

几个关键节点：

1. 逆置前头节点->逆置后尾节点

2. 逆置前尾节点->逆置后头节点
  	3. 逆置前头节点的前驱
     	4. 逆置前尾节点的后继

思路：

找到开始逆置的节点，记录该节点的前驱和该节点；
从head开始，逆置n-m+1个节点；
将pre_head与new_head连接，aft_tail与head连接。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        int len = n - m + 1; // 需要写在改变m之前
        ListNode* res = head; //最终的头节点
        ListNode *pre_head = NULL;//开始逆置的节点的前驱
        while(head && --m) 
        {   
            pre_head = head; //head的前驱
            head = head -> next; //head向后移动m-1个位置
        }
        ListNode* aft_tail = head; //逆置后的尾节点
        ListNode* new_head = NULL; //逆置后的头节点
       
        while(head && len) //逆置m到n
        {
            ListNode *next = head -> next;
            head -> next = new_head;
            new_head = head;
            head = next;
            len--;
        }

        aft_tail -> next = head; //逆置后尾节点的下一个节点是逆置前尾节点的后继
        if(pre_head) pre_head -> next = new_head; //逆置节点的前驱部位空，第一个逆置的不是头节点
        else res = new_head;//从头节点开始逆置的
        return res;
    }
};

146. LRU缓存

题目链接：https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/

思路：

使用两个双链表和一个哈希表：第一个双链表存储未被使用的位置；第二个双链表存储已被使用的位置，且按最近使用时间从左到右排好序；哈希表存储key对应的链表中的节点地址；

class LRUCache {
public:

    struct Node
    {
        int val, key;
        Node *left, *right;
        Node() : key(0), val(0), left(NULL), right(NULL) {}
    };
    Node *hu, *tu; // hu: head_used, tu: tail_used; head在左侧，tail在右侧
    Node *hr, *tr; // hr: head_remains, tr: tail_remains; head在左侧，tail在右侧
    int n;
    unordered_map hash;

    void delete_node(Node *p)
    {
        p->left->right = p->right, p->right->left = p->left;
    }

    void insert_node(Node *h, Node *p)
    {
        p->right = h->right, h->right = p;
        p->left = h, p->right->left = p;
    }
	/*初始化*/
    LRUCache(int capacity) {
        n = capacity;
        hu = new Node(), tu = new Node();
        hr = new Node(), tr = new Node();
        hu->right = tu, tu->left = hu;
        hr->right = tr, tr->left = hr;
		
        //第一个双链表插入 n 个节点，n 是缓存大小；
        //第二个双链表和哈希表都为空；
        for (int i = 0; i val; //如果key存在，则返回对应的value，同时将key对应的节点放到第二个双链表的最左侧；
        }
        return -1; //如果key不存在，则返回-1
    }

    void put(int key, int value) {
        if (hash[key]) //用哈希表判断key是否存在
        {
            //key存在，则修改对应的value，同时将key对应的节点放到第二个双链表的最左侧；
            Node *p = hash[key];
            delete_node(p);
            insert_node(hu, p);
            p->val = value;
            return;
        }
		//key不存在：
		//如果缓存已满，则删除第二个双链表最右侧的节点（上次使用时间最老的节点），同时更新三个数据结构；
        if (!n)
        {
            n ++ ;
            Node *p = tu->left;
            hash[p->key] = 0;
            delete_node(p);
            insert_node(hr, p);
        }
		//否则，插入(key, value)：从第一个双链表中随便找一个节点，修改节点权值，然后将节点从第一个双链表删除，插入第二个双链表最左侧，同时更新哈希表；
        n -- ;
        Node *p = hr->right;
        p->key = key, p->val = value, hash[key] = p;
        delete_node(p);
        insert_node(hu, p);
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

使用一个双链表和一个哈希表

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
        used = 0;
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->pre = head;
    }

    int get(int key) {
        if (m.count(key)) {
            Node *p = m[key];
            int val = p->val;
            delete_node(p);
            m[key] = insert_node(key, val);
            return val;
        }
        return -1;
    }

    void put(int key, int value) {
        if (m.count(key)) {       
            delete_node(m[key]);
            used--;
        }
        m[key] = insert_node(key, value);
        used++;
        if (used > cap) {           
            m.erase(tail->pre->key); 
            delete_node(tail->pre);          
            used--;
        }

    }
private:
    int cap, used;
    struct Node{
        int val, key;
        Node *pre, *next;
        Node(int key, int val): key(key), val(val), pre(NULL), next(NULL){};
    };
    unordered_map m;
    Node *head, *tail;
    void delete_node(Node *p) {
        p->pre->next = p->next;
        p->next->pre = p->pre;    
        delete p;

    }
    Node* insert_node(int key, int val) {
        Node *node = new Node(key, val);
        head->next->pre = node;
        node->next = head->next;
        head->next = node;
        node->pre = head;
        return node;
    }    
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

147. 链表插入排序

题目链接：https://leetcode-cn.com/problems/insertion-sort-list/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        //借助dummy指针
        ListNode* dummy = new ListNode(-1);
        while(head)
        {
            ListNode* next = head -> next;
            ListNode* p = dummy;
            //找到待插入元素的合适位置
            while(p -> next && p -> next -> val  val) p = p -> next;
            //将待插入元素出入到链表中
            head -> next = p -> next;
            p -> next = head;
            head = next;
        }
        return dummy -> next;
    }
};

148. 排序链表

题目链接：https://leetcode-cn.com/problems/sort-list/

快速排序

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //得到尾节点
    ListNode* get_tail(ListNode* head){
        while(head -> next) head = head -> next;
        return head;
    }
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;
        auto left = new ListNode(-1), mid = new ListNode(-1), right = new ListNode(-1);
        auto ltail = left, mtail = mid, rtail = right;
        
        int val = head -> val;
        for(auto p = head; p; p = p -> next)
        {
            if(p -> val  next = p; 
            else if(p -> val == val) mtail  = mtail -> next = p;
            else rtail = rtail -> next = p;
        }
        ltail -> next = mtail -> next = rtail -> next = NULL;
        left -> next = sortList(left -> next);
        right -> next = sortList(right -> next);
        
        //拼接三个链表
        get_tail(left) -> next = mid -> next;
        get_tail(left) -> next = right -> next;
        
        auto p = left -> next;
        // delete left;
        // delete mid;
        // delete right;
        return p;
    }
};

归并排序

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* pre = head, *slow = head, *fast = head;
        while(fast && fast->next) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;
        return mergeTwoList(sortList(head), sortList(slow));
    }
    ListNode* mergeTwoList(ListNode* h1, ListNode* h2) {
        if(!h1) return h2;
        if(!h2) return h1;
        if(h1->val val) {
            h1->next = mergeTwoList(h1->next, h2);
            return h1;
        }
        else {
            h2->next = mergeTwoList(h1, h2->next);
            return h2;
        }
    }
};

143. 重排链表

题目链接：https://leetcode-cn.com/problems/reorder-list/

思路：

将后半段的指针都反向；
用两个指针分别从1和n开始往中间扫描，将后半段交替插入到前半段。

时间复杂度分析：整个链表总共扫描三次，第一次求总长度，第二次将后半段反向，第三次将后半段交替插入前半段，所以总时间复杂度是 O(n)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        //获取链表长度
        int n = 0;
        for (ListNode *p = head; p; p = p->next) n ++ ;
        //长度小于2，不用重排
        if (n next;
        //逆置后半串节点
        ListNode *a = later, *b = later->next;
        while (b)
        {
            ListNode *c = b->next;
            b->next = a;
            a = b;
            b = c;
        }
        //依次将后部分的节点插入到前面正确的位置
        later->next = 0;
        while (head && head != a)
        {
            b = a->next;
            a->next = head->next;
            head->next = a;
            head = head->next->next;
            a = b;
        }
    }
};

141. 环形链表

题目链接：https://leetcode-cn.com/problems/linked-list-cycle/

快慢指针

快指针一次走两步，慢指针一次走一步，当两个指针第一次相遇的时候，快和慢指针一次都走一步，第二次相遇的点就是环的入口。可以证明

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head || !head -> next) return nullptr;
        ListNode* fast = head;
        ListNode* low = head;
        
        while(fast && low)
        {
            fast = fast -> next;
            low = low -> next;
            if(fast) fast = fast -> next;
            //如果快指针走到nullptr，说明链表没有环
            else return false;
            
            //第一次相遇后，令fast = head 两个节点都走一步
            if(fast == low)
            {
                fast = head;
                while(fast != low)
                {
                    fast = fast -> next;
                    low = low -> next;
                }
                return true;
            }
        }
        return false;
    }
};

142 环形链表II

题目链接：

160. 相交链表

题目链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

双指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return nullptr;
        auto A = headA, B = headB;
        while(A != B)
        {
            A = A -> next;
            B = B -> next;
            if(!A && !B) return nullptr;
            if(!A) A = headB;
            if(!B) B = headA;
        }
        return A;
    }
};

86. 分隔链表

题目链接：https://leetcode-cn.com/problems/partition-list/

快速排序中的一步，将元素放到合适的位置，左边比他小，右边比他大或者相等。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //得到left的尾结点
    ListNode* get_tail(ListNode* head){
        while(head -> next) head = head -> next;
        return head;
    }
    ListNode* partition(ListNode* head, int x) {
        if(!head) return head;
        auto left = new ListNode(-1), right = new ListNode(-1);
        auto ltail = left, rtail = right;
        for(auto p = head; p; p = p -> next)
        {
            if(p -> val  next = p;
            else rtail = rtail -> next = p;
        }
        ltail -> next  = rtail -> next = nullptr;
        get_tail(left) -> next = right -> next;
        return left -> next;
    }
};

23. 合并K个有序的链表

题目链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/

顺序合并

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* new_head = new ListNode(-1); //保存合并后的头结点
        ListNode* tmp = new_head; //遍历链表
        while(l1 && l2)
        {
            //小的追加到tmp后面
            if(l1 -> val  val)
            {
                tmp -> next = l1;
                l1 = l1 -> next;
            }
            else
            {
                tmp -> next = l2;
                l2 = l2 -> next;
            }
            //更新tmp
            tmp = tmp -> next;
        }
        //没处理完的直接追加到后面
        tmp -> next = l1 ? l1 : l2;
        return new_head -> next;
    }

    ListNode* mergeKLists(vector& lists) {
        ListNode *ans = nullptr;
        for (size_t i = 0; i

分治合并

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* new_head = new ListNode(-1); //保存合并后的头结点
        ListNode* tmp = new_head; //遍历链表
        while(l1 && l2)
        {
            //小的追加到tmp后面
            if(l1 -> val  val)
            {
                tmp -> next = l1;
                l1 = l1 -> next;
            }
            else
            {
                tmp -> next = l2;
                l2 = l2 -> next;
            }
            //更新tmp
            tmp = tmp -> next;
        }
        //没处理完的直接追加到后面
        tmp -> next = l1 ? l1 : l2;
        return new_head -> next;
    }
    ListNode* merge(vector& lists, int l, int r)
    {
        if(l == r) return lists[l];
        if(l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

234. 回文链表

题目链接：https://leetcode-cn.com/problems/palindrome-linked-list/

逆置链表

逆置链表的后半部分然后比较

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head -> next) return true;
        auto slow = head, fast = head;
        while(fast && fast -> next)
        {
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        
        fast = nullptr; //逆置后的头节点 逆置前的尾节点
        while(slow)
        {
            auto next = slow -> next;
            slow -> next = fast;
            fast = slow;
            slow = next;
        }
        while(head && fast)
        {
            if(head -> val != fast -> val) return false;
            head = head -> next;
            fast = fast -> next;
        }
        delete slow;
        delete fast;
        return true;
    }
};

小技巧

fast一次走2步，slow一次走1步，链表全长为len，len为偶数时，slow到达前半段的最后一个节点，len为奇数时，slow到达正中间的节点，两种情况中，slow->next均为后半段的起始节点。

ListNode* getMid(ListNode* head){
    ListNode* fast = head, * slow = head;
    while(fast && fast -> next){
        slow = slow->next;
        fast = fast->next->next;
    }
    delete fast;
    return slow;
}

2. 两数相加

题目链接：

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

题目链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/submissions/

/**
 * 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(-1);
        dummy -> next = head;
        auto fast = dummy, low = dummy;
        while(fast)
        {
            fast = fast -> next;
            if(n >= 0) n--;
            else low = low -> next;
        }
        return dummy -> next;
    }
};

21. 合并两个有序链表

题目链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/submissions/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* tmp = dummy;
        while(l1 && l2)
        {
            if(l1 -> val  val) 
            {
                tmp -> next = l1;
                l1 = l1 -> next;
            }
            else 
            {
                tmp -> next = l2;
                l2 = l2 -> next;
            }
            tmp = tmp -> next;
        }
        tmp -> next = l1 ? l1 : l2;
        return dummy -> next;
    }
};

876. 链表的中间节点

题目链接：https://leetcode-cn.com/problems/middle-of-the-linked-list/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        auto fast = head, low = head;
        while(fast  && fast -> next)
        {
            low = low -> next;
            fast = fast -> next -> next;    
        }
        return low;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        dummy -> next = head;
        auto fast = dummy, low = dummy;
        while(fast -> next  && fast -> next -> next)
        {
            low = low -> next;
            fast = fast -> next -> next;    
        }
        return low -> next;

    }
};

114. 二叉树展开为链表

题目链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

递归

在还没操作节点右子树前，不能破坏该节点的右子树指向。所以采用后序遍历。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  TreeNode* last = nullptr;
    void flatten(TreeNode* root) {
        if (root == nullptr) return;
        flatten(root->right);
        flatten(root->left);
        root->right = last;
        root->left = nullptr;
        last = root;
    }

};

迭代(先序遍历)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        //先序遍历
        stack node_stack;
        if(nullptr != root){
          node_stack.push(root);
        }

        TreeNode* current_node = root;

        while(!node_stack.empty()){
          TreeNode *node = node_stack.top();
          node_stack.pop();
 
          if(nullptr != node->right){
              node_stack.push(node->right);
          }

          if(nullptr != node->left){
              node_stack.push(node->left);
          }

          if(node != root){
             current_node->left = nullptr;
             current_node->right = node;
          }
          current_node = node;
        }
    }
};

总结

链表的问题比较考察逻辑思维，可以通过画图来理清思路。

常用操作

获取链表中间位置的元素

ListNode* getMid(ListNode* head){
    ListNode* fast = head, * slow = head;
    while(fast && fast -> next){
        slow = slow->next;
        fast = fast->next->next;
    }
    delete fast;
    return slow;
}

删除倒数第K个节点

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(-1);
    dummy -> next = head;
    auto fast = dummy, low = dummy;
    while(fast)
    {
        fast = fast -> next;
        if(n >= 0) n--;
        else low = low -> next;
    }
    return dummy -> next;
}

逆置链表

ListNode* reverseList(ListNode* head) {
    ListNode *new_head = nullptr;
    while(head)
    {
        ListNode *next = head->next;
        head->next = new_head;
        new_head = head;
        head = next;
    }
    return new_head;
}

技巧和注意事项

指针丢失和内存泄漏

插入节点

插入之前，应该先把要插入位置之前的元素c的下一个节点保存下来

/*
a -> b -> c -> d -> e
c后面插入f
*/
//写法1
cur = c -> next;
c -> next = f;
f -> next = cur;

//写法2
f -> next = c -> next;
c -> next = f;

删除节点

p -> next  = p -> next -> next;

（哨兵）dummy节点

用来解决边界问题，不参与业务逻辑，引入链表以后，不管链表是否为空，dummy->next为头结点；

边界问题

1. 链表为空

2. 链表只包含一个节点

3.链表只包含两个节点

4. 链表对头尾节点的处理

【算法】【链表】链表相关问题总结

标签：双向数据结构 solution roo 业务逻辑 strong content intersect res

原文地址：https://www.cnblogs.com/Trevo/p/12941011.html

上一篇：java基础知识01

下一篇：JavaScript计算每个字母出现的次数

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【算法】【链表】链表相关问题总结
文章链接：http://soscw.com/index.php/essay/41835.html

亲，登录后才可以留言！

【算法】【链表】链表相关问题总结

剑指offer

6. 从尾到头打印链表

递归

栈

reverse数组

18. 删除链表的节点

22. 链表中倒数第k个节点

快慢指针

24. 反转链表

思路

25. 合并两个排序的链表

35. 复杂链表的复制

哈希

迭代

36. 二叉搜索树与双向链表

递归

Leetcode

92. 反转链表II

146. LRU缓存

147. 链表插入排序

148. 排序链表

快速排序

归并排序

143. 重排链表

141. 环形链表

快慢指针

142 环形链表II

160. 相交链表

双指针

86. 分隔链表

23. 合并K个有序的链表

顺序合并

分治合并

234. 回文链表

逆置链表

2. 两数相加

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

21. 合并两个有序链表

876. 链表的中间节点

114. 二叉树展开为链表

递归

迭代(先序遍历)

总结

常用操作

获取链表中间位置的元素

删除倒数第K个节点

逆置链表

技巧和注意事项

指针丢失和内存泄漏

插入节点

删除节点

（哨兵）dummy节点

边界问题

1. 链表为空

2. 链表只包含一个节点

3.链表只包含两个节点

4. 链表对头尾节点的处理

评论

热门文章

推荐文章

最新文章

置顶文章