输入一个链表,反转链表后,输出新链表的表头。-笔试面试资料

这是qklbishe.com第6036 篇笔试面试资料
提供答案分析,通过本文《输入一个链表,反转链表后,输出新链表的表头。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:
输入一个链表,反转链表后,输出新链表的表头。

输入一个链表,反转链表后,输出新链表的表头。 writezen
public class So

   查看全部

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;     } }

2016-05-13 20:59:38 回复(95)
输入一个链表,反转链表后,输出新链表的表头。 搁浅的鱼儿
//第一种方法是:非递归方法 /* 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号
这是我的,很简单
    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)
简单模拟题。。。这种问题代码越简单越清晰吧。。不要写太复杂了。。
/* 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指向的是还没有反转的链表的头部:

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

初始状态是newHead指向nullcurrentHead指向的是第一个元素,一直往后遍历直到newHead指向最后一个元素为止:

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

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

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

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

我的答案

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

思路:
  • 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 回复(7)
输入一个链表,反转链表后,输出新链表的表头。 枪骑兵叔叔
使用一个栈来解决问题,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)
输入一个链表,反转链表后,输出新链表的表头。 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
两种解法:
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)
输入一个链表,反转链表后,输出新链表的表头。 区块链毕设学生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、

/* * 使用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

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)
输入一个链表,反转链表后,输出新链表的表头。 区块链毕设学生984423号
/*  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
/**  * 反转链表  * 题目描述  * 输入一个链表,反转链表后,输出链表的所有元素。  *  * @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
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

/*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)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 输入一个链表,反转链表后,输出新链表的表头。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情