LeetCode刷题---链表

发布时间:2024年01月12日

一、反转链表

在这里插入图片描述

1.分析

给定单链表头结点,反转链表之后返回新的头结点。
思路一:翻转指针
在这里插入图片描述
原本1号指针指向下一个节点2的,但是将1号指针翻转之后指向空,一直翻转直到5指向空翻转为5指向4.
所以我们就需要3个变量,一个节点存放指向其他节点的信息,另一个节点是被指向的节点,还需要一个节点来存放下一个节点的信息
思路2:头插法
将已知链表存放在一个新的链表中,将已知链表的每一个节点头插进新的链表中,需要三个变量:一个变量存放新的链表的节点信息,一个变量存放下一个节点的信息,一个变量来存放当前位置的信息

2.翻转指针

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* n1 = NULL;//被指向的节点
    struct ListNode* n2 = head;//已知节点
    struct ListNode* n3 = n2->next;//存下一个节点的位置
    while (n2 != NULL)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
        {
            n3 = n3->next;
        }
    }
    return n1;
}

3.头插法

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

二、链表的中间结点

在这里插入图片描述

1.分析

给定链表头结点,找出链表中间节点。
思路1:求长度,找中间值
定义一个变量len来表示长度,先遍历一遍链表,求出链表长度,然后直接就可以得出中间节点的位置
思路2:快慢指针
定义两个指针,一个slow一个fast,fast走两步,slow走一步,当fast到达最后一个节点或者fast出了链表之后,slow指针刚好到达中间节点,图示:
在这里插入图片描述
在这里插入图片描述

1.求长度,找中点

struct ListNode* middleNode(struct ListNode* head) {
    int len = 0;
    struct ListNode* p1 = head;
    while (p1)
    {
        len++;
        p1 = p1->next;
    }
    for (int i = 0;i < len / 2;i++)
    {
        head = head->next;
    }
    return head;
}

2.快慢指针

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

三、合并两个有序链表

在这里插入图片描述

1.分析

思路1:尾插法
由上图可知可以创建一个新的链表,然后依次把两个链表中小的数尾插进新的链表,准备两个节点,一个节点遍历新的链表,一个节点始终指向新链表的头结点,用两个链表依次比较来填充新的链表
思路2:带哨兵位的头结点
利用带哨兵位的头结点,就排除了第一个指针为空的情况,就可以直接判断两个链表的val的大小。

2.尾插法

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }
    struct ListNode* head = NULL, * tail = NULL;
    while (list1 != NULL && list2 != NULL)
    {
        if (list1->val < list2->val)
        {
            if (tail == NULL)
            {
                head = tail = list1;
            }
            else
            {
                tail->next = list1;
                tail = tail->next;
            }
            list1 = list1->next;
        }
        else
        {
            if (tail == NULL)
            {
                head = tail = list2;
            }
            else
            {
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;
        }
    }
    if (list1 != NULL)
    {
        tail->next = list1;
    }
    if (list2 != NULL)
    {
        tail->next = list2;
    }
    return head;
}

注:可以提前准备头结点,省去两个判断是否为空的if语句
算法优化:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }
    struct ListNode* head = NULL, * tail = NULL;
    if (list1->val < list2->val)
    {
        head = tail = list1;
        list1 = list1->next;
    }
    else
    {
        head = tail = list2;
        list2 = list2->next;
    }
    while (list1 != NULL && list2 != NULL)
    {
        if (list1->val < list2->val)
        {
            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
    }
    if (list1 != NULL)
    {
        tail->next = list1;
    }
    if (list2 != NULL)
    {
        tail->next = list2;
    }
    return head;
}

3.带哨兵位的头节点

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }
    struct ListNode* head = NULL, * tail = NULL;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while (list1 != NULL && list2 != NULL)
    {
        if (list1->val < list2->val)
        {
            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
    }
    if (list1 != NULL)
    {
        tail->next = list1;
    }
    if (list2 != NULL)
    {
        tail->next = list2;
    }
    return head->next;
}

四、环形链表

在这里插入图片描述

1.分析

思路:通过快慢指针,创建两个指针,一个fast指针,一个slow指针,slow指针一次走一步,fast指针一次走两步,因为fast指针走的快,所有有两种情况。
第一种情况:
在这里插入图片描述
第二种情况:
在这里插入图片描述
第二种情况就是环形链表,因为fast走的快所以fast先进入环形区域,所以fast在环形区域中已知旋转,当slow进入环形区域中时solw和fast最终会相遇,所以结束标志就是fast==slow如果是非环形链表的话直接就出循环了。

2.快慢指针

bool hasCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast)
        {
            return true;
        }
    }
    return false;
}
文章来源:https://blog.csdn.net/2301_79969994/article/details/135500033
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。