首页 > 试题广场 > 反转链表
[编程题]反转链表
输入一个链表,反转链表后,输出链表的所有元素。

734个回答

添加回答
// 利用栈 改变值的方法:
ListNode* ReverseList(ListNode* pHead) {
	if (!pHead)
		return nullptr;
	stack<int> s;
	ListNode *p = pHead;
	while (p){
		s.push(p->val);
		p = p->next;
	}
	p = pHead;
	while (s.size()){
		int tmp = s.top();
		s.pop();
		p->val = tmp;
		p = p->next;
	}
	return pHead;
}
// 直接改变指针的方法:

ListNode* ReverseList(ListNode* pHead) {
	ListNode *pre = pHead;
	ListNode *sub = pHead->next;
	if (!pHead)	// 输入为空
		return NULL;
	if (!sub)	// 只有一个节点
		return pHead;

	// 多于一个节点
	while (sub){				
		ListNode *aft = sub->next;
		if (pre == pHead){			// 若pre是头节点,则它的next要置为空
			pre->next = NULL; 
		}				

		sub->next = pre;	// 后面节点指向前面节点.
		pre = sub;			// 

		if (aft != NULL)
			sub = aft;
		else
			break;
	}
	return pre;
}

// 精简一下代码:
ListNode* ReverseList(ListNode* pHead) {
	ListNode *pre = NULL;
	ListNode *node = pHead;
	while (node){
		ListNode *tmp = node->next;
		node->next = pre;
		pre = node;
		if (tmp)
			node = tmp;
		else
			break;
	}
	return node;
}

编辑于 2017-09-14 11:34:27 回复(0)
更多回答
推荐
public class So
   查看全部
编辑于 2015-06-19 16:46:40 回复(28)
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;
    }
}

编辑于 2016-05-13 20:59:38 回复(30)
//第一种方法是:非递归方法
/*
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 回复(23)
这是我的,很简单
    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 回复(26)
两种解法:

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 回复(5)
简单模拟题。。。这种问题代码越简单越清晰吧。。不要写太复杂了。。
/*
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 回复(6)
每次循环的情况写出来,假设初始链表是 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 回复(3)
使用一个栈来解决问题,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 回复(4)

反转链表是很基本的操作
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 回复(3)
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)
/*
 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 回复(1)
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 回复(1)
思路:
  • 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 回复(1)
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 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        
         if(head == null)
                return null;
      //记录当前节点的前一个节点
         ListNode prenode = null;
         //记录当前节点的后一个节点
         ListNode aftnode = head.next;
         //当前节点
         ListNode innode = head;
         //将头节点改为尾节点
         head.next = null;
         prenode = head;
         //指针指向下一个节点
         head = aftnode;
         
         while(head !=null){
          //1.记录该节点的后一个节点
          //2.将该节点的next指向前一个节点
          //3.将该节点的指针后移
          //4.修改该移动后的pre节点。
          aftnode = head.next;
          head.next = prenode;
          prenode = head;
          head = aftnode;
          
         }
         
         return prenode;
       
    }
}

发表于 2015-09-08 15:07:01 回复(2)
好像没看到递归的写法,递归倒序输出简单 


public class Test { static class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } @Override public String toString() { return "ListNode [val=" + val + ", next=" + next + "]"; } } static ListNode ReverseList(ListNode head) { ListNode root = fun(head); head.next = null;// 最开始的节点已经是最后一个节点了,需要设置next为空 return root; } // 1.递归,ac static ListNode fun(ListNode me) { ListNode next = me.next; ListNode re; if (next != null) { re = fun(next); next.next = me; } else { re = me; } System.out.println(me.val); return re; } // 2.循环,没有倒序输出,懒得写了 static ListNode fun2(ListNode me) { ListNode t = me, last = null, next = null; while (t != null) { next = t.next; t.next = last; last = t; t = next; } return last; } public static void main(String[] args) { ListNode root = new ListNode(1); ListNode item = new ListNode(2); ListNode item2 = new ListNode(3); item.next = item2; root.next = item; System.out.println(ReverseList(root)); } }


编辑于 2015-10-08 17:56:06 回复(0)
//头像 //
class Solution {
public:
 ListNode* ReverseList(ListNode* pHead) {
        ListNode *pre, *cur, *nex;
        pre = nullptr;
        cur = nex = pHead;
        while( nex!=nullptr )
        {
            nex = nex->next;
            cur->next = pre;
            pre = cur;
            cur = nex;
        }
        return pre;
 }
}; 

发表于 2015-06-08 12:20:00 回复(2)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode oldhead = head;
        ListNode newhead = head.next;
        head.next = null;
        while (newhead != null) {
            ListNode next = newhead.next;
            newhead.next = oldhead;
            oldhead = newhead;
            newhead = next;
        }
        
        return oldhead;
    }
}

发表于 2017-09-20 22:25:33 回复(0)
// 反转链表:递归
ListNode* reverse(ListNode* head) {
	if (head == NULL || head->next == NULL) {
		return head;
	}
	ListNode* node = reverse(head->next);
	head->next->next = head;
	head->next = NULL;
	return node;
}

// 反转链表:非递归
ListNode* reverse(ListNode* head) {
	ListNode* pre = NULL;
	ListNode* next = NULL;
	while (head != NULL) {
		next = head->next;
		head->next = pre;
		pre = head;
		head = next;
	}
	return pre;


发表于 2017-09-14 00:22:57 回复(0)
package test;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 输入一个链表,反转链表后,输出链表的所有元素。
 */
public class Solution1 {

    //方法1:使用ArrayList作为中介
    public static ListNode ReverseList(ListNode head) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        ListNode temp = head;
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        temp.next = null;
        ListNode t = temp;
        for (int i = list.size()-1; i >= 0; i--){
            temp.val = list.get(i);
            temp = temp.next;
        }
        return t;
    }

    //方法2:使用栈结构做中介
    public static ListNode ReverseList1(ListNode head) {
        Stack<Integer> stack = new Stack<Integer>();
        ListNode temp = head;
        while(temp != null){
            stack.push(temp.val);
            temp = temp.next;
        }
        ListNode t = head;
        while (!stack.isEmpty()){
            head.val = stack.pop();
            head = head.next;
        }
        return t;
    }
}


发表于 2017-09-12 19:45:51 回复(0)
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        static int i = 0;
        static ListNode * pNewHead;
        i++; //递归嵌套层数
        ListNode * p;
        if(pHead == NULL || pHead->next == NULL) {
            pNewHead= pHead; //记录翻转后头结点
            i--;
            return pHead;
        }
        else {
            p = ReverseList(pHead->next);
            p->next = pHead;
            pHead->next = NULL;
        }
        i--;
        if(i > 0)
    return pHead; //未完全退出返回当前节点
        else
            return pNewHead; //完全退出返回头节点
    }
};
前面大神只给了大概算法解题思路,但代码是直接运行不起来,要真正完成整个链表反转,还应该加点东西:
1.记录当前递归嵌套层数,只有还存在嵌套时,函数应该返回的是当前节点,而当完全退出时,我们期望返回的是头结点。
2.头结点使用一个static变量,当第一遍遍历到链表尾节点的时候,反转之后,该尾节点便是头结点,记录输出即可。
发表于 2017-09-11 11:54:44 回复(0)
牛客网,程序员必备求职神器
QQ群:169195721
微 信:www_nowcoder_com 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋