剑指offer代码解析——面试题16反转单链表

本题的详细解析均在代码中注释:

/**
 * 题目:将单链表反转,并输出反转后链表的头结点
 * @author 大闲人柴毛毛
 */
public class RevertLink {
	/**
	 * 分析:本题是要将链表“反转”,而不是反向输出,这点要特别注意。
	 * 反转需要改变链表的结构,使所有指针都指向相反方向;
	 * 而反向输出不需要改变链表结构,只需反向输出即可。
	 * 对于反向问题可使用栈来实现,可参见我的博客《剑指offer——面试题5》,这里不再赘述。
	 * 下面来解决反转问题。 
	 */
	
	/**
	 * 反转单链表其实就是将链表中的指针指向相反方向,
	 * 若a1和a2是单链表中两个相邻的结点,未反转前的状态是:a1.next = a2,
	 * 现在进行反转:a2.next = a1.
	 * 此时,虽然a2指向了a1,但链表出现了“断裂”,a2和它的后继结点发生了断裂,无法继续进行反转操作。
	 * 因此,我们需要再增加一个指针a3,指向a2的后继结点。
	 * 当反转完a2结点后,从a3开始继续依次向后进行反转操作,直到整个链表反转完为止。
	 * 代码如下:
	 */
	
	/**
	 * 反转链表
	 * @param first 链表的头结点
	 * @return 返回反转后链表的头结点
	 */
	public static <T> Node<T> revertLink(Node<T> first){
		//当链表为空时
		if(first==null){
			System.out.println("链表为空!");
			return null;
		}
		
		//当链表只有一个结点时
		if(first.next==null){
			return first;
		}
		
		//当链表只有两个结点时
		if(first.next.next==null){
			//end为链表的尾结点,是反转后的头结点
			Node<T> end = first.next;
			//将第二个结点的next域指向第一个结点
			first.next.next = first;
			//将第一个结点的next域设置null
			first.next = null;
			return end;
		}
		
		//当链表有三个及以上结点时
		{
			Node<T> a1 = first;//a1指向头结点
			Node<T> a2 = first.next;//a2指向第二个结点
			Node<T> a3 = first.next.next;//a3指向第三个结点
		
			//将头结点的后继设为null
			first.next = null;
			
			//不停的将a1->a2反转为a2->a1,直到a3为空
			while(a3!=null){
				//a2的后继设为a1
				a2.next = a1;
				//a1、a2、a3依次向后移一位
				a1 = a2;
				a2 = a3;
				a3 = a3.next;
			}
			
			//将最后一个结点反向
			a2.next = a1;
			return a2;
		}
		//PS:这里使用局部代码块一方面增强了代码的可读性,另一方面使得局部代码块中的变量能够在代码块结束之后立即释放,从而节约了内存空间。
	}
}


/**
 * 定义结点 
 */
class Node<T>{
	public T data;
	public Node<T> next;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏有趣的Python

算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重...

2686
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题26复杂链表的复制

本题详细解析均在代码注释中: /** * 题目:请复制一个复杂链表。每个结点除了有一个next指针指向下一个结点外,还有一个sibling指向链表中的任意一个...

2514
来自专栏weixuqin 的专栏

数据结构学习笔记(线性表)

2725
来自专栏用户画像

5.2.4 邻接多重表

在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边,或需要对边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低。

491
来自专栏编程理解

数据结构(二):二叉搜索树(Binary Search Tree)

二分法的查找过程是,在一个有序的序列中,每次都会选择有效范围中间位置的元素作判断,即每次判断后,都可以排除近一半的元素,直到查找到目标元素或返回不存在,所以

211
来自专栏小二的折腾日记

牛客网-剑指offer-2

二叉树是觉得很烦的东西了,比链表复杂很多,看着头都有点疼啊,但是没办法,生活就是这样,只有把不会的会了才会进步,怕的变得不怕才能越来越厉害。 常规的理解一下:二...

662
来自专栏文武兼修ing——机器学习与IC设计

树与二叉表达树树基础二叉表达树

树基础 定义 数的定义 可以使用递归的方法定义:一棵树是一些节点的集合。一棵树由根节点和0~多个非空树(即子树)组成。这些子树中的每一颗根节点都被来自母树跟的一...

2646
来自专栏Vamei实验室

纸上谈兵: 左倾堆 (leftist heap)

我们之前讲解了堆(heap)的概念。堆是一个优先队列。每次从堆中取出的元素都是堆中优先级最高的元素。 在之前的文章中,我们基于完全二叉树(complete bi...

2829
来自专栏用户画像

6.3.2 B+树基本概念

2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

712
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题17合并两个排序的链表

本题的详细解析均在代码注释中: /** * 题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。 * @author 大闲人...

3777

扫描关注云+社区