Leetcode算法题（链表的中间节点+返回倒数第k个节点+合并两个有序链表）

熬夜学编程的小王

发布于 2024-11-20 20:24:18

9100

代码可运行

文章被收录于专栏：编程小王编程小王

运行总次数：0

代码可运行

题目1：

本题力扣链接：https://leetcode.cn/problems/middle-of-the-linked-list/solutions/164351/lian-biao-de-zhong-jian-jie-dian-by-leetcode-solut/

思路1：单指针法

首先我们对链表进行遍历，记录链表的总长度N，再进行遍历原链表，返回刚跳出循环大于N/2时，对应的链表节点，即为中间节点。

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* pcur=head;
    if(head==NULL)
    {
        return head;
    }
    int count=0;
    while(pcur)
    {
        count++;
        pcur=pcur->next;
    }
    pcur=head;
    int k=0;
    while(k<count/2)
    {
        k++;
        pcur=pcur->next;
    }
    return pcur;
}

思路2：快慢指针法

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

场景1：

场景二：

题目2：

OJ链接：

思路1：反转链表+遍历

先将原链表进行翻转，再将反转后的链表的头结点移动k-1位，最后直接返回此时节点的值。

typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k){
    //1. 先将原链表进行翻转
    //2. 再将反转后的链表的头结点移动k-1位
    ListNode* n1,*n2,*n3;
    n1=NULL,n2=head,n3=n2->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        n3=n3->next;
    }
    k=k-1;
    while(k--)
    {
        n1=n1->next;
    }
    return n1->val;
}

复杂度分析：

时间复杂度：O(N),其中N为给定链表节点的数目。

空间复杂度：O(1)

思路2：遍历+挪动

先计算原链表的总长度s，再将原链表的头结点移动s-k位，返回此时节点对应的值。

typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k){
    ListNode* pcur=head;
    int s=0;
    while(pcur)
    {
        s++;
        pcur=pcur->next;
    }
    int m=s-k;
    while(m--)
    {
        head=head->next;
    }
    return head->val;

}

复杂度分析：

时间复杂度：O(N),其中N为给定链表节点的数目。

空间复杂度：O(1)

题目3：

思路：遍历+尾插+比较

创建新的带头链表，依次遍历两个原链表，比较对应的值，尾插到新的链表尾部。

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL) {
        return list2;
    }
    if (list2 == NULL) {
        return list1;
    }
    ListNode* newlist,*newhead;
     newhead=newlist=(ListNode*)malloc(sizeof(ListNode));
    while (list1 && list2) {
        if (list1->val > list2->val) {
            newlist->next = list2;
            list2 = list2->next;
        } else {
            newlist->next = list1;
            list1 = list1->next;
        }
        newlist = newlist->next;
    }
    if (list1)
        newlist->next = list1;
    if (list2)
        newlist->next = list2;
    return newhead->next;
}

如果本文章对你有帮助，期待你的三连！！！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-20，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历