leedcode 链表

算法 leedcode

发布日期: 2021-06-18

leedcode 链表

链接

删除链表中的节点

题目解析

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为要被删除的节点。

题目解析

懒得解析了

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

题目描述

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

进阶：你能尝试使用一趟扫描实现吗？

题目解析方法一

为头节点head建立一个前驱结点heeaad,这样就不怕只有head一个结点的情况了。先遍历一遍链表得到链表的长度，再从heeaad遍历链表，r->next，指向的是当前应该删除的结点。记住不要让r指向当前应该删除的结点，不然含需要一个r的前驱节点。

class Solution
{
public:
    int getLength(ListNode *head)
    {
        int length = 0;
        while (head)
        {
            length++;
            head = head->next;
        }
        return length;
    }
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        int length = getLength(head);
        if (length == 0)
            return NULL;
        n = length + 1 - n;                       //正数
        ListNode *heeaad = new ListNode(0, head); //声明一个指向head结点的结点，值为零
        ListNode *r = new ListNode;
        r = heeaad;
        for (int i = 1; i <= n - 1; i++)
        {
            r = r->next;
        }
        //得到当前要删除的为 r->next
        r->next = r->next->next;
        ListNode *ans = heeaad->next;
        delete heeaad;
        return ans;
    }
};

题目解析方法二

使用栈，向将链表中的所有数据先存起来，然后依次从前面插入。

反转链表

题目描述

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

题目解析方法一

遍历一遍，从左到右依次设置三个指针t1 t2 t3。
每一个循环中的装填都是 t2已经设置好指向，t2需要改变指向到t1，t3指向下一轮循环需要改变的结点。

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <utility>
#include <map>
#include <stack>
using namespace std;

struct ListNode
{
    int val;
    struct ListNode *next;
};

struct ListNode *reverseList(struct ListNode *head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    ListNode *t1 = NULL, *t2 = NULL, *t3 = NULL;
    t1 = head;
    t2 = head->next;
    t1->next = NULL;
    do
    {
        t3 = t2->next;
        t2->next = t1;
        if (t3 == NULL)
        {
            return t2;
        }
        t1 = t2;
        t2 = t3;
        t3 = t3->next;
    } while (1);
    return NULL;
}

题目解析方法二

递归

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <utility>
#include <map>
#include <stack>
using namespace std;

struct ListNode
{
    int val;
    struct ListNode *next;
};

struct ListNode *reverseList(struct ListNode *head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    struct ListNode *res = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return res;
}

合并有序链表

题目描述

合并两个递增链表

题目解析方法一

迭代，先设立一个伪头节点，比较l1 l2的大小，将游标指向小的，并后移对应链表l1或l2，直到一个为空

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <utility>
#include <map>
#include <stack>
#include <malloc.h>
#include <random>
#include <time.h>
using namespace std;

struct ListNode
{
    int val;
    struct ListNode *next;
};

struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2)
{
    struct ListNode *res = (struct ListNode *)malloc(sizeof(struct ListNode));
    res->next = NULL;
    struct ListNode *t = res;
    while (1)
    {
        if (l1 == NULL)
        {
            t->next = l2;
            return res->next;
        }
        if (l2 == NULL)
        {
            t->next = l1;
            return res->next;
        }
        if (l1->val <= l2->val)
        {
            t->next = l1;
            l1 = l1->next;
            t = t->next;
        }
        else
        {
            t->next = l2;
            l2 = l2->next;
            t = t->next;
        }
    }
}

题目解析方法二

递归

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <utility>
#include <map>
#include <stack>
#include <malloc.h>
#include <random>
#include <time.h>
using namespace std;

struct ListNode
{
    int val;
    struct ListNode *next;
};

struct ListNode *mergeTwoLists(struct ListNode *l1, struct 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(l2->next, l1);
        return l2;
    }
}

回文链表

题目描述

判断一个链表是否是回文链表

题目解析方法一

将链表从中间分为两部分，将其中一部分进行反转，顺序比较是否相等。

这个解法和力扣官方解法的快慢指针相同。

在并发环境中这个解法需要进行链表访问的锁定，因为在访问中会进行更改链表。

在程序的最后还需要将链表复原。

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <utility>
#include <map>
#include <stack>
#include <malloc.h>
#include <random>
#include <time.h>
using namespace std;

struct ListNode
{
    int val;
    struct ListNode *next;
};

struct ListNode *reverseList(struct ListNode *head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    struct ListNode *res = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return res;
}

bool isPalindrome(struct ListNode *head)
{
    int count = 0;
    struct ListNode *h = head;
    while (h)
    {
        count++;
        h = h->next;
    }
    count /= 2;
    struct ListNode *l1 = head;
    struct ListNode *l2 = head;
    while (count > 0)
    {
        count--;
        l2 = l2->next;
    }
    l2 = reverseList(l2);
    while (l1 && l2)
    {
        if (l1->val != l2->val)
        {
            return false;
        }
        l1 = l1->next;
        l2 = l2->next;
    }
    return true;
}

题目解析方法二

复制到数组里面，这个方法太幼稚了。略。

题目解析方法三

递归，使用后序遍历的递归。由于递归天然具有从后向前的特性，所以用来从后向前遍历是再好不过的。在函数外设置一个变量用来指示从前向后遍历进行并比较的结点。

struct ListNode *now = NULL;

bool check(struct ListNode *head)
{
    if (head)
    {
        if (!check(head->next))
            return false;
        if (head->val != now->val)
        {
            return false;
        }
        now = now->next;
    }
    return true;
}

bool isPalindrome(struct ListNode *head)
{
    now = head;
    return check(head);
}

环形链表

题目描述

判断一个链表是否有环，即遍历永远不会结束。

题目解析方法一

这是一个投机的方法。根据是系统分配内存是从小开始分配。不可以在真实环境中使用。

bool hasCycle(struct ListNode *head)
{
    if (head == NULL || head->next == NULL)
    {
        return false;
    }
    while (head->next)
    {
        if (head->next <= head)
            return true;
        head = head->next;
    }
    return false;
}

题目解析方法二

使用哈希表记录每一次遍历到的结点地址。遍历时判断是否已经遍历过。

bool hasCycle(struct ListNode *head)
{
    unordered_set<struct ListNode *> set;
    while(head)
    {
        if(set.count(head))
            return true;
        set.insert(head);
        head=head->next;
    }
    return false;
}

题目解析方法三

快慢指针

使用两个指针兔子和乌龟兔子一次走两步，乌龟一次走一步，直到结尾。若相遇说明有环。

bool hasCycle(struct ListNode *head)
{
    if (head == NULL || head->next == NULL)
        return false;
    struct ListNode *tu, *gui;
    gui = head;
    tu = head->next;
    while (tu && gui)
    {
        if (tu == gui)
            return true;
        gui = gui->next;
        tu = tu->next;
        if (tu == NULL)
            return false;
        else
            tu = tu->next;
    }
    return false;
}

崔文耀

http://myblog.cuimouren.cn

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源崔文耀 !

leedcode 链表

计算机网络期末复习

2021-06-19 期末复习计算机网络

计算机网络

leedcode 字符串

2021-06-17 算法 leedcode

leedcode 字符串

leedcode 链表

leedcode 链表

删除链表中的节点

题目解析

题目解析

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

题目描述

题目解析 方法一

题目解析 方法二

反转链表

题目描述

题目解析 方法一

题目解析 方法二

合并有序链表

题目描述

题目解析 方法一

题目解析 方法二

回文链表

题目描述

题目解析 方法一

题目解析 方法二

题目解析 方法三

环形链表

题目描述

题目解析 方法一

题目解析 方法二

题目解析 方法三

题目解析方法一

题目解析方法二

题目解析方法一

题目解析方法二

题目解析方法一

题目解析方法二

题目解析方法一

题目解析方法二

题目解析方法三

题目解析方法一

题目解析方法二

题目解析方法三