首页 > 试题广场 > 反转链表
[编程题]反转链表
  • 热度指数：1047814 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入一个链表，反转链表后，输出新链表的表头。
示例1

输入

{1,2,3}

输出

{3,2,1}

说明：本题目包含复杂数据结构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 回复(52)
我就用这个名字了头像 我就用这个名字了
Java   循环操作   详细思路 
public class Solution {
    public ListNode ReverseList(ListNode head) {
      
        if(head==null)
            return null;
        //head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
    	ListNode pre = null;
        ListNode next = null;
        //当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
        //需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
        //即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
        //所以需要用到pre和next两个节点
        //1->2->3->4->5
        //1<-2<-3 4->5
        while(head!=null){
            //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
            //如此就可以做到反转链表的效果
            //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            //保存完next，就可以让head从指向next变成指向pre了，代码如下
            head.next = pre;
            //head指向pre后，就继续依次反转下一个节点
            //让pre，head，next依次向后移动一个节点，继续下一次的指针反转
            pre = head;
            head = next;
        }
        //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }
}

编辑于 2021-01-20 17:13:50 回复(97)
搁浅的鱼儿头像 搁浅的鱼儿 
//第一种方法是：非递归方法
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		
        if(pHead==NULL) return NULL;//注意程序鲁棒性
        
        ListNode* pNode=pHead;//当前指针
        ListNode* pReverseHead=NULL;//新链表的头指针
        ListNode* pPrev=NULL;//当前指针的前一个结点
        
        while(pNode!=NULL){//当前结点不为空时才执行
            ListNode* pNext=pNode->next;//链断开之前一定要保存断开位置后边的结点
            
            if(pNext==NULL)//当pNext为空时，说明当前结点为尾节点
                pReverseHead=pNode;
 
            pNode->next=pPrev;//指针反转
            pPrev=pNode;
            pNode=pNext;
        }
        return pReverseHead;
    }
}

//第二种方法是：递归方法 /*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		//如果链表为空或者链表中只有一个元素	
        if(pHead==NULL||pHead->next==NULL) return pHead;
        
		//先反转后面的链表，走到链表的末端结点
        ListNode* pReverseNode=ReverseList(pHead->next);
        
        //再将当前节点设置为后面节点的后续节点
        pHead->next->next=pHead;
        pHead->next=NULL;
        
        return pReverseNode;
        
    }
};
递归的方法其实是非常巧的，它利用递归走到链表的末端，然后再更新每一个node的next 值 ，实现链表的反转。而newhead 的值没有发生改变，为该链表的最后一个结点，所以，反转后，我们可以得到新链表的head。

注意关于链表问题的常见注意点的思考：

1、如果输入的头结点是 NULL，或者整个链表只有一个结点的时候

2、链表断裂的考虑

编辑于 2016-06-27 15:52:55 回复(41)
睿博远航头像 睿博远航
看了一下好像没有python的非递归实现。思路很简单：1->2->3->4->5，遍历链表，把1的next置为None，2的next置为1，以此类推，5的next置为4。得到反转链表。需要考虑链表只有1个元素的情况。图中有具体的每步迭代的思路，最后输出pre而不是cur是因为最后一次迭代后cur已经指向None了，而pre是完整的反向链表。 
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead==None or pHead.next==None:
            return pHead
        pre = None
        cur = pHead
        while cur!=None:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

发表于 2018-06-14 18:29:37 回复(19)
牛客829441号头像 牛客829441号
这是我的，很简单 
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
        	next = head.next;
        	head.next = pre;
        	pre = head;
        	head = next;
        }
		return pre;
    }

发表于 2016-02-16 09:14:35 回复(45)
马客(Mark)头像 马客(Mark)
简单模拟题。。。这种问题代码越简单越清晰吧。。不要写太复杂了。。 
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* h = NULL;
        for(ListNode* p = pHead; p; ){
            ListNode* tmp = p -> next;
            p -> next = h;
            h = p;
            p = tmp;
        }
        return h;
    }
};

发表于 2015-08-22 22:42:12 回复(14)
Java
我去个地方啊头像 我去个地方啊

题目描述

输入一个链表，反转链表后，输出新链表的表头。

解题思路

一开始学的时候看的答案就是这个方法，显然是要比递归好的，但是如果不理解的话，光靠背很容易出错，并且也不大背的上，如今重温这道题，其实是很简单的，我们下面用图示来阐述。

主要的思想是用两个指针，其中newHead指向的是反转成功的链表的头部，currentHead指向的是还没有反转的链表的头部：

image

初始状态是newHead指向null，currentHead指向的是第一个元素，一直往后遍历直到newHead指向最后一个元素为止：

image

下面展示的是其中某个时间点的指向细节：

image

理解了上面的图示，程序就呼之欲出了。

我的答案

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode newHead = null;
        ListNode currentHead = head;
        if(head == null || head.next == null){
            return head;
        }

        while(currentHead != null){
            ListNode next = currentHead.next;
            currentHead.next = newHead;
            newHead = currentHead;
            currentHead = next;
        }

        return newHead;
    }
}
发表于 2019-03-07 11:35:30 回复(3)
Java
杨！一叶知秋头像 杨！一叶知秋

// 这里采用一种递归的方式，从链表节点的尾部进行反转指针即可。仔细体会，递归的简练。
代码如下：

public class Solution {
    public ListNode ReverseList(ListNode head) {
           if(head == null || head.next == null) {
             return head;
         }
         ListNode preNode = ReverseList(head.next);
         head.next.next = head;
         head.next = null;
         return preNode;
    }
}
发表于 2018-06-06 15:49:26 回复(8)
Python
Yannyezixin头像 Yannyezixin
思路：
  • pHead始终指向要反转的结点
  • last 指向反转后的首结点
  • 每反转一个结点，把pHead结点的下一个结点指向last, last指向pHead成为反转后首结点, 再把pHead向前移动一个结点直至None结束 
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return pHead
        
        last = None
        
        while pHead:
            tmp = pHead.next    
            pHead.next = last
            last = pHead
            pHead = tmp
        
        return last

发表于 2016-07-25 07:08:05 回复(8)
elvishao头像 elvishao
每次循环的情况写出来，假设初始链表是 0 -> 1 -> 2 -> 3 -> 4
// 0 -> 1 -> 2 -> 3 -> 4   oldHead指向0， newHead指向0，toBeReversed指向1
// 1 -> 0 -> 2 -> 3 -> 4   oldHead指向0， newHead指向1，toBeReversed指向2
// 2 -> 1 -> 0 -> 3 -> 4  oldHead指向0， newHead指向2，toBeReversed指向3
// 3 -> 2 -> 1 -> 0 -> 4   oldHead指向0， newHead指向3，toBeReversed指向4
// 4 -> 3 -> 2 -> 1 -> 0   oldHead指向0， newHead指向4，toBeReversed指向null
public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode oldHead = head;
        ListNode newHead = head;
        ListNode toBeReversed = head.next;
        do {
            oldHead.next = toBeReversed.next;
            toBeReversed.next = newHead;
            newHead = toBeReversed;
            toBeReversed = oldHead.next;
        } while (toBeReversed!=null);
        return newHead;
}
发表于 2016-03-25 22:02:42 回复(4)
fuyufjh头像 fuyufjh
两种解法：

1、三个指针在链表上同时滑动，比较容易想到但是编码略复杂 

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == NULL) return NULL;
        if (pHead->next == NULL) return pHead;
         
        ListNode *pBefore = pHead, *p = pHead->next, *pAfter = p->next;
        while (pAfter) {
            p->next = pBefore; // reverse
            pBefore = p;
            p = pAfter;
            pAfter = pAfter->next;
        }
        p->next = pBefore;
        pHead->next = NULL;
        return p;
    }
};
2、从原链表的头部一个一个取节点并插入到新链表的头部 

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == NULL) return NULL;
        ListNode* head = pHead;
        pHead = pHead->next;
        head->next = NULL;
        while (pHead) {
            ListNode *next = pHead->next;
            pHead->next = head;
            head = pHead;
            pHead = next;
        }
        return head;
    }
};

发表于 2015-08-04 09:43:40 回复(8)
枪骑兵叔叔头像 枪骑兵叔叔
使用一个栈来解决问题，C++ 
/*struct ListNode {
  int val;
  struct ListNode *next;
  ListNode(int x) :
      val(x), next(NULL) {
  }
};*/
class Solution {
public:
  ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL||pHead->next == NULL)
        {
            return pHead;
        }
        ListNode * p=pHead;
        ListNode * newHead;
        stack<ListNode *> stack1;
        while(p->next!=NULL)
        {
            stack1.push(p);
            p=p->next;
        }
        newHead = p;
        while(!stack1.empty())
        {
          p->next=stack1.top();
            p=p->next;
            stack1.pop();
        }
        p->next=NULL;
        return newHead;
  }
};

编辑于 2015-04-22 14:46:15 回复(17)
牛客252411号头像 牛客252411号

反转链表是很基本的操作
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode ReverseList(ListNode head) {
  ListNode cur=head;
        ListNode pre=null;
        ListNode next=null;
        while(cur!=null)
            {
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    } 
}

发表于 2015-11-15 21:58:55 回复(5)
C/C++
卷积神经网络哦头像 卷积神经网络哦

需要三个指针相互赋值移动完成

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL) return NULL;
        ListNode *last = pHead, *nex = pHead->next, *cur = nex;
        last->next = NULL; //头结点指向NULL
        while(cur != NULL){
            nex = cur->next;
            cur->next = last;
            last = cur;
            cur = nex;
        }
        return last;
    }
};
发表于 2018-11-28 11:22:32 回复(0)
Java
Dio、头像 Dio、 
/*
* 使用Java栈的方式，这里的注意点是原来的头结点的next需要置为null，否则会导致遍历时无限循环，导致超时
*/
		public ListNode ReverseList(ListNode head) {
			if (head == null)
				return null;

			Stack<ListNode> stack = new Stack<ListNode>();
			ListNode temp = head;
			do {
				stack.push(temp);
				temp = temp.next;
			} while (temp != null);
			
			//关键在于这里，原来的头结点的next要置为空，否则导致遍历时无限循环
			head.next = null;

			ListNode root = stack.pop();
			ListNode node = root;
			while (!stack.isEmpty()) {
				node.next = stack.pop();
				node = node.next;
			}
			return root;
		}

发表于 2017-05-23 17:47:24 回复(6)
夕一啊头像 夕一啊 
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		if(pHead == NULL || pHead->next == NULL) {
            return pHead;
        }
        ListNode* last=NULL;
        ListNode* now=NULL;       
       while(pHead){
            
            now=pHead;   //问题就在这，两个指针指向同一个地址，now改变，pHead就变了
            now->next=last;
            last=now;
            pHead=pHead->next;
        }
        return now;
//-------------------------------------------上面的不行，下面的可以
       ListNode* next=NULL;
        while(pHead){           
            next=pHead->next;//其实三个指针指向三个地方
            pHead->next=last;
            last=pHead;
            pHead=next;
            
        }
        return last;
            
    }
};
写出来这个我思考很久终于得到的答案。
看起来我之前写的代码逻辑没有问题，和正确答案一样，用了三个指针。pHead 本来是想一直走到重点的，然后now和last不断跟过来，但是我让now和 pHead相等了。然后改变now->next， pHead的next也为空了，所以结果错误了
发表于 2017-03-26 22:18:43 回复(0)
C/C++
anybody头像 anybody 
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		if (pHead == NULL || pHead->next == NULL)
			return pHead;
		ListNode *pre = pHead;
		ListNode *cur = pHead->next;
		while (cur)
		{
			ListNode *post = cur->next;
			cur->next = pre;
			pre = cur;
			cur = post;
		}
		pHead->next = NULL;
		return pre;
    }
};

发表于 2016-07-21 23:59:18 回复(2)
ellie2dina头像 ellie2dina 
/*
 public class ListNode {
 int val;
 ListNode next = null;

 ListNode(int val) {
 this.val = val;
 }
 }*/
public class Solution {
	public ListNode ReverseList(ListNode head) {
		if (head == null)
			return null;
		if (head.next == null)
			return head;

		ListNode pPre = null;
		ListNode p = head;
		ListNode pNext = head.next;
		ListNode newHead = null;

		while (p != null) {
			pNext = p.next;//一定要记录下来后面的节点
			if (pNext == null)
				newHead = p;
			p.next = pPre;//这里的方向已经转变
			pPre = p;
			p = pNext;//将保存的后面的节点作为下一次循环的p

		}
		return newHead;

	}
}

发表于 2015-09-13 18:18:28 回复(2)
shijiacheng头像 shijiacheng 
/**
 * 反转链表
 * 题目描述
 * 输入一个链表，反转链表后，输出链表的所有元素。
 *
 * @author shijiacheng
 * @date 2018/2/23
 */
public class ReverseListSolution {
    /**
     * 依次遍历所有节点，将所有节点的next指向前一个节点
     */
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;//持有下一个节点的引用
            head.next = pre;//将当前节点对下一个节点的引用指向前一个节点
            pre = head;//将前一个节点指向当前节点
            head = next;//将当前节点指向下一个节点
        }
        return pre;
    }
}
发表于 2018-02-23 15:47:43 回复(0)
郑斌coder头像 郑斌coder 
public class Solution {
    public ListNode ReverseList(ListNode head) {
		ListNode front = null, q = null;
        while(head != null) {
            q = head.next;
            head.next = front;
            front = head;
            head = q;
        }
        head = front;
        return head;
    }
}

发表于 2016-07-12 08:20:12 回复(1)
JavaScript
xfzxy头像 xfzxy 
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function ReverseList(pHead)
{
    // write code here
    if(!pHead) return null;
    var pre = pHead;  // 定义上一个节点
    var head = pHead; // 定义当前节点
    while(head) {
        // 如果存在当前节点
        // 将当前节点的下一个节点用next保存
        let next = head.next;
        // 让当前节点指向next，变为指向pre（上一个节点）
        head.next = pre;
        // 上面两步实现了一节链表的反转，下面，将pre，head，next依次后移一位，再次反转
        pre = head;
        head = next;
    }
    // 将反转后的链表尾部（对应开始未反转链表的头部）设为null
    pHead.next = null;
    // 返回新链表的表头
    return pre;
}

发表于 2019-09-04 11:23:31 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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