关于链表的经典OJ题1-阿里云开发者社区

关于链表的经典OJ题1

2022-11-29 90

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 关于链表的经典OJ题

1.反转单链表：请你反转链表，并返回反转后的链表。

例图：

思路一：

疑问1：为什么不是n3==NULL停止循环了？？？

疑问2：要是链表为空了

答：要是链表为空了，直接返回NULL

注：重复的过程一般是用循环解决

循环三要素：初识值，迭代过程，结束条件

思路一代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)
    return NULL;
    //初始化
    struct ListNode* n1 = NULL,*n2 = head,*n3 = n2->next;
    //结束条件
    while(n2)
    {
        //迭代过程（重复过程）
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
        n3 = n3->next;
    }
    return n1;
}

思路二：头插法

思路二代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)
    {
        return NULL;
    }
   struct ListNode *cur = head,*next = cur->next;
   struct ListNode* newhead = NULL;
   while(cur)
   {
       cur->next = newhead;
       newhead = cur;
       cur = next;
       if(next)
       next = next->next;
   }
   return newhead;
}

2.链表的中间结点：

给定一个头结点为head的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

例1:输入【1,2,3,4,5】输出：3

例2：输入【3,4,5,6】输出：5

思路：

大家从上面的思路中也可以看出它也是迭代的过程，初始条件是slow，fast都指向第一个结点，迭代过程，slow走一步，fast走两步，结束条件fast->next,fast只要有一个为空就结束。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode *slow = head,*fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

3.合并两个有序链表：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
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)
    {
        tail->next = list1;
    }
    if(list2)
    {
        tail->next = list2;
    }
    return head;
}