首页 > 试题广场 >

反转链表

[编程题]反转链表
  • 热度指数：1773237 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围：
要求：空间复杂度 ，时间复杂度 。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
示例1

输入

{1,2,3}

输出

{3,2,1}
示例2

输入

{}

输出

{}

说明

空链表则输出空

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
推荐
writezen头像 writezen 
public class Solution {
 public static ListNode ReverseList(ListNode head) {
 if(head==null)
 return null;
 ListNode reversedHead=null;
 ListNode current=head;
 ListNode tmp=null;
 ListNode pre=null;
 while(current!=null){
 tmp=current.next;
 current.next=pre;
 if(tmp==null)
 reversedHead=current;
            pre=current;
 current=tmp;
 
 }
 return reversedHead;
 }
}

编辑于 2015-06-19 16:46:40 回复(64)
C
牛客217792980号头像 牛客217792980号 
struct ListNode* ReverseList(struct ListNode* head ) {
	struct ListNode* prev = NULL;
	while(head) {
		struct ListNode* next = head->next;
		head->next = prev;
		prev = head;
		head = next;
	}
	return prev;
}

发表于 2024-06-14 16:15:15 回复(0)
C
冰糖雪离头像 冰糖雪离
struct ListNode* ReverseList(struct ListNode* head ) {
   struct ListNode* p1,*p2,*p3;
   p1 = head;
   p2 = p1->next;
   if(head == NULL || head->next == NULL)
    {
        return head;
    }
    else
    {
   while(p2!= NULL)
   {
     p1->next = p2->next;
     p2->next = head;
     head = p2;
     p2 = p1->next;
   }
   return head;
}
}
发表于 2024-05-02 16:02:29 回复(0)
C
牛客174984708号头像 牛客174984708号
struct ListNode* ReverseList(struct ListNode* head ) {
    // write code here
struct ListNode* prv=NULL;
struct ListNode* curr=head;
while(curr!=NULL){
   struct ListNode* next=curr->next;
   curr->next=prv;
   prv=curr;
   curr=next;
}
return prv;
}
发表于 2024-04-27 21:30:56 回复(0)
C
南宫梦凝头像 南宫梦凝 
容易理解的

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* head ) {
    // write code here
    struct ListNode* p1,*p2;
    if(head == NULL || head ->next == NULL){
        return head;
    }else{
        p1 = head;
        p2 = head->next;
        head = p2->next;
        p2->next = p1;
        p1->next =NULL;
        while(head!=NULL){
            p1 = p2;
            p2 = head;
            head = p2->next;
            p2->next = p1;
        }
        return p2;
    }

}

编辑于 2024-03-31 11:41:20 回复(0)
C
徐文达头像 徐文达 
struct ListNode* ReverseList(struct ListNode* head ) 
{
    //空链表与只有一个结点的链表都无需进行操作
    if(head == NULL || head->next == NULL)
    {
        return head;
    }

    struct ListNode* pcur = head;
    struct ListNode* prev = NULL;
    struct ListNode* pnext = head;

    //反转链表，将后驱指针更新为前驱指针
    while(pcur != NULL)
    {
        pnext = pcur->next;
        pcur->next = prev;
        prev = pcur;
        pcur = pnext;
    }

    return prev;
}

编辑于 2024-03-28 11:25:24 回复(0)
C
我没有会员头像 我没有会员 
我这为啥会报错误啊？大佬们
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* head ) {
    // write code here
    struct ListNode* pre, *end, *p;
    int num = 0;
    if (head == NULL || head->next == NULL) {//若只有一个元素或者空链表，直接返回
        return head;;
    }
    pre = head;
    while (pre->next->next != NULL) {
        pre = pre->next;//将pre指针指向倒数第二个元素
    }
    end = pre->next;//end指针指向最后一个元素
    p = pre;//p指针指向倒数第二个元素
    pre = head;//将pre指针指向第一个元素
    while (pre != end) {//交换pre指针和end指针的数据域，p指针始终指向end指针指向元素的前驱节点
        num = end->val;
        end->val = pre->val;
        pre->val = num;

        pre = pre->next;
        end = p;
        p = head;
        while (p->next != end) {
            p = p->next;
        }
    }
    return head;
}

编辑于 2024-03-23 21:01:32 回复(0)
C
牛客183552821号头像 牛客183552821号
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @return ListNode类
 */
#include <stdio.h>
struct ListNode* ReverseList(struct ListNode* head ) {
    struct ListNode *last=head;
    struct ListNode *a=NULL;
    struct ListNode *b=NULL;
    struct ListNode *c=NULL;
    if(head==NULL)
    return NULL;
    else
    while(true)
    {
        if(last->next!=NULL)
        {
            a=last->next;
            last->next=b;
            b=last;
            last=a;
        }
        else {
            a=last->next;
            last->next=b;
            b=last;
            last=a;
            return b;
        }

    }
    // write code here
}
编辑于 2024-03-22 14:38:29 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
struct ListNode* ReverseList(struct ListNode* head ) {
    struct ListNode *res;
    if((head==NULL) || (head->next==NULL))
        return head;
    res = ReverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return res;
}

发表于 2024-03-15 21:42:19 回复(0)
C
斯科菲头像 斯科菲 
采用c语言双指针的方法

核心理解为：将链表的箭头反向调转，达到反转链表，即节点的指针指向前驱节点

struct ListNode* ReverseList(struct ListNode* head ) {
    // write code here
    struct ListNode* cur;
    struct ListNode* pre;
    struct ListNode* temp;
    if(head == NULL){
        //如果为空链表，则输出为空链表
        pre = NULL;
    }else{
        cur = head;//初始化指向头节点
        pre = NULL;//指向头节点的前一个节点，即NULL
        while(cur){
            temp = cur->next;//保存后继节点
            cur->next = pre;//指向前驱节点
            pre = cur;//pre向后移动一节点
            cur = temp;//cur向后移动一节点
        }
    }
    return pre;//返回反转后的头节点
}

编辑于 2024-03-13 17:50:50 回复(0)
C
夜雨潇湘人断肠头像 夜雨潇湘人断肠
struct ListNode* reserve(struct ListNode** phead)
{
    struct ListNode*head=*phead;
    struct ListNode*nest=head->next;
    head->next=NULL;
    while(nest->next)
    {
        struct ListNode*nnest=nest->next;
        nest->next=head;
        head=nest;
        nest=nnest;
    }
    nest->next=head;
    return nest;

}
struct ListNode* ReverseList(struct ListNode* head ) {
    struct ListNode*hhead = head;
    int len = 0;
    while(hhead)
    {
        hhead = hhead->next;
        len++;
    }
    if(len==0)
    {
        return NULL;
    }
    else if(len==1)
    {
        return head;
    }
    else
    {
    struct ListNode* phead=reserve(&head);
    return phead;
    }
   
}
发表于 2024-02-27 17:23:11 回复(1)
C
weing头像 weing 
struct ListNode* ReverseList(struct ListNode* head ) {
    // write code here
    struct ListNode* resu_list;
    struct ListNode* p;
    struct ListNode* temp;
    if(head == NULL){
        resu_list = NULL;
    }else{
        resu_list = head;
        p = head->next;
        resu_list->next = NULL;
        while(p != NULL){
            temp = p->next;
            p->next = resu_list;
            resu_list = p;
            p = temp;
        }
    }
    return resu_list;
}


编辑于 2024-02-21 18:04:45 回复(0)
C
牛客114648446号头像 牛客114648446号 
#include <stdio.h>
struct ListNode* ReverseList(struct ListNode* head ) {
    struct ListNode* temp,* temp2,*temp3,*temp4;
    if (head==NULL){
        return head;
    }
    else {
        temp2=head->next;
        temp=head;
        while (temp2!=NULL){
            temp3=temp2->next;
            temp4=temp2;
            temp2->next=temp;
            temp2=temp3;
            temp=temp4; 
        }
        head->next=NULL;
        head=temp;
        return head;
    }       
}

注意值传递方式

编辑于 2024-02-05 19:00:51 回复(0)
C
牛客864724317号头像 牛客864724317号
C语言递归 
struct ListNode* Reverse(struct ListNode* cur, struct ListNode* pre) {
    if (cur == NULL) return pre;
    struct ListNode* temp = NULL;
    temp = cur-> next;
    cur->next = pre;
    return Reverse(temp, cur);
}

struct ListNode* ReverseList(struct ListNode* head ) {
    return Reverse(head, NULL);
}

发表于 2024-01-13 20:43:15 回复(2)
C
吾王初心头像 吾王初心
//使用的是头插法，直接反转构建新链表
struct ListNode* cerateNode(int val){
    struct ListNode * tenmp = (struct ListNode*)malloc(sizeof(struct ListNode));
    tenmp->next = NULL;
    tenmp->val = val;
    return tenmp;
}

struct ListNode* ReverseList(struct ListNode* head ) {
    // write code here
    struct ListNode * q = NULL;
    if(head == NULL)
        return q;
    else{
        struct ListNode * p = head;
        while (p) {
            if(q == NULL){
                q = cerateNode(p->val);
            }else {
                struct ListNode * t = cerateNode(p->val);
                t->next = q;
                q = t;
            }
            p = p->next;
        }
    }
    return q;
}
编辑于 2024-01-01 01:23:47 回复(0)
C
Ysing头像 Ysing 
struct ListNode* ReverseList(struct ListNode* head ) 
{
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    struct ListNode* next = NULL;
    
    while (curr != NULL) 
        {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

这段代码使用三个指针prev、curr和next来迭代地将链表中的节点依次反转。prev指向已反转的部分链表的头节点，curr指向待反转的节点，next用于保存curr的下一个节点。

在每次迭代中，先将curr的下一个节点保存到next中，然后将curr的next指针指向prev，实现反转。之后，将prev指向curr，curr指向next，继续进行下一次迭代。

当迭代结束时，prev指向的节点就是反转后的链表的头节点，将其返回即可。


编辑于 2023-12-05 16:52:40 回复(0)
提交观点

问题信息

链表
来自：寻找时间黑客在线编程大...
难度：
90条回答 336293浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号