leetcode刷题日记:206. Reverse Linked List(反转链表)

2024-01-03 08:49:20

此题要进行反转链表,我们可以先进行链表的遍历找到链表的总长度,然后设置一个链表头指向新建立的链表,然后使用for循环一个一个的将元素加入到新链表之中。这种做法的时间复杂度为O(n2)时间复杂度较高。
图示如下:
在这里插入图片描述
在这里插入图片描述
依次进行即可将链表进行反转。
下面给出一个可行的利用递归实现的算法:

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *p=NULL, *q=NULL, *s=NULL;
    if(head==NULL){
        return p;
    }
    p = reverseList(head->next);
    q = p;
    s = (struct ListNode *)malloc(sizeof(struct ListNode));
    s->val = head->val;
    s->next = NULL;
    while(p!=NULL){
        if(p->next == NULL){
            p->next = s;
            break;
        }
        p = p->next;
    }
    if(p==NULL){
        q = s;
    }
    return q;
}

运行结果截图:
在这里插入图片描述
我们想一想有没有更好的算法呢?你想一下我们可以直接在原始链表上进行操作吗,利用指针将链表元素之间两两反转,这样是不是也能得到一个反转的链表。
而且指针两两反转只需要三个指针就行,而且时间复杂为为O(n)
图示如下:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
如图所示我们就得到了一个反转的链表。代码如下:

struct ListNode* reverseList(struct ListNode *head){
    struct ListNode *p, *q, *s;
    p = head;
    if(p==NULL){
        return p;
    }
    if(head->next!=NULL){
        q = head->next;
        s = q->next;
    }else{
        return head;
    }
    p->next = NULL;
    while(q){
        q->next = p;
        p = q;
        q = s;
        if(s!=NULL){
            s = s->next;
        }
    }
    return p;
}

运行结果截图:
在这里插入图片描述

文章来源:https://blog.csdn.net/apprentice_eye/article/details/134488934
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。