链表OJ题讲解1

2023-08-23 61

版权

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

简介： 我们可以遍历一遍链表，然后将等于val的值的节点删除了，然后在将剩余的链接起来即可。我们就需要两个指针，一个遍历链表另一个记录上一个节点的位置，如果相等就删除链接，等到链表遍历结束，就可以得到新的链表，但是这种放大有一个弊端，就是如果头结点就是val我们无法处理，所以我们需要现将头结点是val的情况处理了，头结点是val，我们只需要头删即可。

删除链表元素

方法一

我们可以遍历一遍链表，然后将等于val的值的节点删除了，然后在将剩余的链接起来即可。我们就需要两个指针，一个遍历链表另一个记录上一个节点的位置，如果相等就删除链接，等到链表遍历结束，就可以得到新的链表，但是这种放大有一个弊端，就是如果头结点就是val我们无法处理，所以我们需要现将头结点是val的情况处理了，头结点是val，我们只需要头删即可。

代码如下：

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev = NULL,*cur = head;
    while(cur)
    {
        if(cur->val==val)
        {
            //相等就要删除
            if(cur==head)
            {
                //如果头结点是就相等，就要头删
                head = cur->next;
                free(cur);
                cur = head;
            }
            else
            {
                //正常删除
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {
            // 不相等prev记录上一个节点，cur往下走
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

方法二

我们可以依旧是遍历原链表，但是我们这一次需要一个新的头，然后与val不相等的我们尾插到新的头中就可以了，这个方法比较省事，直接尾插就可以，但是需要注意新的头为空的情况，为了方便尾插，我们需要一个尾指针来记录尾节点的位置。

代码如下：

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur = head,*tail=NULL,*newhead=NULL;
    while(cur)
    {
        if(cur->val==val)
        {
            //相等就删除
            struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
        else
        {
            //不相等就尾插
            if(newhead==NULL)
            {
                //第一次尾插
                newhead = tail = cur;
                cur= cur->next;
            }
            else
            {
                //正常尾插
                tail->next= cur;
                cur = cur->next;
                tail = tail->next;
            }
        }
    }
    //尾差的最有后一个节点的next要置NULL，不然可能会非法访问
    if(tail!=NULL)
    //tail等于空说明链表为空，或者链表中的元素都val
        tail->next = NULL;
    return newhead;
}

反向链表

方法一

我们定义一个空指针，然后翻转链表的指向，但是直接翻转的话我们会丢失下一个节点，所以我们还需要一个指针来记录下一个节点的位置。

代码如下：

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newhead = NULL,*cur = head,*next = NULL;
    while(cur)
    {
        //next指向下一个节点
        next = cur->next;
        //翻转指向
        cur->next = newhead;
        //更新新的头结点
        newhead = cur;
        //更新cur
        cur = next;        
    }
    return newhead;
}

方法二

头插法，我们遍历原链表，然后把节点都头插到新的头处，即可翻转链表。

代码如下：

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newhead = NULL,*cur = head;
    while(cur)
    {
        //保存下一个节点
        struct ListNode* next = cur->next;
        //头插
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

链表的中间结点

这个题使用快慢指针就可以解决。我们让慢指针一次走一步，快指针一次走两步，我们就可以知道当快指针为空时，或者当快指针的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;
}

链表中倒数第k个结点

这个题同样使用快慢指针，我们可以让快指针先走k步，然后两个指针一起走，当快指针为空时，慢指针就是倒数第k个节点，如果先让快指针走k-1步的话，当快指针的next为空时，慢指针就是倒数第k个节点。这两种方法都可以。我们实现走k步的

代码如下：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast = pListHead,*slow = pListHead;
    while(k--)
    {
        // fast=NULL前K个就为空了(判断k是不是过大，以及链表是不是空链表)
        if(fast==NULL) return NULL;
        fast = fast->next;
    }
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

合并两个排序列表

这个题我们可以同时遍历两个链表，然后拿小的下来尾插，思想差不多就是这样，我们需要一个头，但是这个头可以是哨兵位，也可以是空，我们这里写两个版本的。

带哨兵位的

代码如下：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
  //如果一个链表为空直接返回另一个链表
    if(list1==NULL) return list2;
    if(list2==NULL) return list1;
    //创建哨兵位
    struct ListNode* newhead = NULL,*tail = NULL;
    newhead = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while(list1&&list2)
    {
        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 = list2;
    if(list2==NULL) tail->next = list1;
    //保返回的头
    struct ListNode* next = newhead->next;
    //释放哨兵位
    free(newhead);
    return next;
}

不带哨兵位

代码如下：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    //如果一个链表为空直接返回另一个链表
    if(list1==NULL) return list2;
    if(list2==NULL) return list1;
    struct ListNode* newhead = NULL,*tail = NULL;
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            //判断头结点是否为空
            if(newhead==NULL)
            {
                newhead = tail = list1;
                list1 = list1->next;
            }
            else
            {
                tail->next = list1;
                tail = tail->next;
                list1= list1->next;
            }
        }
        else
        {
            //判断头结点是否为空
            if(newhead==NULL)
            {
                newhead = tail = list2;
                list2 = list2->next;
            }
            else
            {
                tail->next = list2;
                tail = tail->next;
                list2= list2->next;
            }
        }
    }
    //如果一个链表为空，直接将另一个链表链接过来
    if(list1==NULL) tail->next = list2;
    if(list2==NULL) tail->next = list1;
    return newhead;
}