链表的反转是常见的面试题目。本文总结了2种方法。
1 定义
单链表node的数据结构定义如下:
class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } }
2 方法1:就地反转法
2.1 思路
把当前链表的下一个节点pCur插入到头结点dummy的下一个节点中,就地反转。
dummy->1->2->3->4->5的就地反转过程:
dummy->2->1->3->4->5 dummy->3->2->1->4->5 dummy->4>-3->2->1->5 dummy->5->4->3->2->12.2 解释
1初始状态
2 过程
pCur是需要反转的节点。
- prev连接下一次需要反转的节点
- 反转节点pCur
- 纠正头结点dummy的指向
- pCur指向下一次要反转的节点
伪代码
1 prev.next = pCur.next; 2 pCur.next = dummy.next; 3 dummy.next = pCur; 4 pCur = prev.next;
3 循环条件
pCur is not null
2.3 代码
1 // 1.就地反转法 2 public ListNode reverseList1(ListNode head) { 3 if (head == null) 4 return head; 5 ListNode dummy = new ListNode(-1); 6 dummy.next = head; 7 ListNode prev = dummy.next; 8 ListNode pCur = prev.next; 9 while (pCur != null) { 10 prev.next = pCur.next; 11 pCur.next = dummy.next; 12 dummy.next = pCur; 13 pCur = prev.next; 14 } 15 return dummy.next; 16 }
2.4 总结
- 1个头结点,2个指针,4行代码
- 注意初始状态和结束状态,体会中间的图解过程。
3 方法2:新建链表,头节点插入法
3.1 思路
新建一个头结点,遍历原链表,把每个节点用头结点插入到新建链表中。最后,新建的链表就是反转后的链表。
3.2 解释
1 初始状态
2 过程
pCur是要插入到新链表的节点。
pNex是临时保存的pCur的next。
- pNex保存下一次要插入的节点
- 把pCur插入到dummy中
- 纠正头结点dummy的指向
- pCur指向下一次要插入的节点
伪代码
1 pNex = pCur.next 2 pCur.next = dummy.next 3 dummy.next = pCur 4 pCur = pNex
3 循环条件
pCur is not null
3.3 代码
1 // 2.新建链表,头节点插入法 2 public ListNode reverseList2(ListNode head) { 3 ListNode dummy = new ListNode(-1); 4 ListNode pCur = head; 5 while (pCur != null) { 6 ListNode pNex = pCur.next; 7 pCur.next = dummy.next; 8 dummy.next = pCur; 9 pCur = pNex; 10 } 11 return dummy.next; 12 }
3.4 总结
- 1个头结点,2个指针(包含一个临时保存节点的pNex),4行代码
- 注意初始状态和结束状态,体会中间的图解过程。
相关推荐
设计一个将输入数据建立成链表、输出链表数据、利用原空间把链表反转的程序代码。
基于linkedList实现自己的双向链表反转。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。...
在“java链表反转及排序”这个主题中,我们将探讨如何在Java中实现单向链表的反转和排序。首先,我们创建一个链表节点类,包含数据和指向下一个节点的引用: ```java public class ListNode { int val; // 节点值 ...
链表反转是链表操作中的一项基本技能,它涉及到链表节点之间的指针调整,使得链表的顺序与原顺序相反。本文将详细解析链表反转的原理以及C/C++语言下的实现方法。 ### 链表反转原理 链表由一系列节点组成,每个...
C语言数据结构link链表反转的实现 在计算机科学中,链表是一种常用的数据结构,它由一系列节点组成,每个节点都包含一个值和一个指向下一个节点的指针。链表反转是指将链表的节点顺序颠倒的操作,即将链表的头节点...
链表反转程序C++ 运行良好,简单,高效,实用的程序
在这个基于Java实现的单链表基本操作中,我们将重点关注链表反转这一特定操作。 链表反转是编程面试中常见的问题,它要求我们改变链表中节点的顺序,使得原链表的最后一个节点成为新链表的第一个节点,原链表的第一...
c++链表的反转,创建链表,插入链表,链表反转,可下载直接运行。
链表反转
在面试中,双向链表反转问题常被用来测试候选人的数据结构和算法理解能力。了解并能够熟练实现这样的操作对于Java开发者来说非常重要,特别是在处理复杂数据结构和优化性能时。通过理解和实践这些概念,你可以更好地...
### C++链表的反转知识点解析 #### 一、链表基本概念 链表是一种常见的数据结构...通过上述代码示例,我们可以清晰地理解链表反转的具体实现过程及其背后的逻辑。这些知识点对于深入学习数据结构和算法具有重要意义。
### 链表反转知识点详解 #### 一、单向链表反转原理及实现 **1.1 基本概念** 单向链表是一种线性数据结构,每个元素包含两个部分:数据域和指向下一个元素的指针域。单向链表的特点是只能从前向后遍历。 **1.2 ...
链表 链表_基于Java的单链表基本操作之链表反转
【链表操作】如链表反转和有序链表合并是常见的面试题目,也是编程练习的重点。这些操作通常需要对指针或引用有深入的理解。链表反转涉及到改变节点的指针方向,而有序链表合并则需要在保持顺序的同时合并两个已排序...
Java实现单向链表反转 Java实现单向链表反转是指将单向链表的顺序颠倒,例如原链表为A->B->C->D->E->F,反转后变为F->E->D->C->B->A。这种操作在实际开发中非常有用,例如在数据处理、数据分析等领域。 单向链表...
K个一组的链表反转
链表反转将单链表的链接顺序反转过来例如:输入:1->2->3->4->5输出:5->4->3->2->1使用两种方式解题* @return 返回倒序后的链表头部
链表反转是常见的面试题,主要考察程序员对基本数据结构的操作能力和逻辑思维能力。这里我们将详细讨论两种链表反转的方法。 首先,我们来看最常用的一种方法,即迭代法。迭代法的基本思想是使用三个指针pre、cur和...
206. 链表反转206. 反转链表 — Easy题目描述示例:解题思路头插法,每次从原链表的头部取下一个节点,利用头插法将其插入新链表的头部图不应该这么画,h