【剑指offer】面试题24：反转链表

梦里梦外; 2022-03-30 14:47 193阅读 0赞

> **题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。**

牛客网连接： [https://www.nowcoder.com/questionTerminal/75e878df47f24fdc9dc3e400ec6058ca][https_www.nowcoder.com_questionTerminal_75e878df47f24fdc9dc3e400ec6058ca]

解决与链表相关的问题总是有大量的指针操作，而指针操作的代码总是容易出错的。很多的面试官喜欢出链表相关的问题，就是想通过指针操作来考察应聘者的编码功底。为了避免出错，我们最好先进行全面的分析。在实际软件开发周期中，设计的时间通常不会比编码的时间短。**在面试的时候我们不要急于动手写代码，而是一开始仔细分析和设计，这将会给面试官留下好的印象。与其给出一段漏洞百出的代码，倒不如仔细分析再写出鲁棒性好的代码**。

为了正确的反转一个链表，需要调整链表中指针的方向。为了将调整指针这个复杂的过程分析清楚，我们可以借助图形来直观的分析。在图中所示的链表中，h, i, j是3个相邻的结点。假设经过若干的操作，我们已经把结点h之前的指针调整完毕，这些结点的next都指向前面的一个结点。接下来我们把i的next指向h，此时的链表结构如图b所示。

![20190106174245716.png][]

不难注意到，由于结点 i 的next指向了它的前一个结点，导致我们无法在链表中遍历到结点 j。为了避免链表在结点 i 处断开，我们需要在调整结点 i 的next之前把结点 j 保存下来。

也就是说我们在调整结点 i 的 next 指针时，除了需要知道结点 i 本身之外，还需要知道 i 的前一个结点h，因为我们需要把结点 i 的next 指向结点 h，同时，我们还要事先保存 i 的下一个结点 j，以防止链表断开。因此相应地我们需要三个指针，分别指向当前遍历到的结点，它的前一个结点和后一个结点。

最后我们试着找到反转链表的头结点。不难分析出反转后的链表的头结点是原始链表的尾节点。什么结点是尾节点，自然是 next 为 null 的结点。

分析写出下面的代码：

public class ReverseLinkedList {
    
    	class ListNode{
    		private int val;
    		private ListNode next = null;
    		
    		public ListNode(int val){
    			this.val = val;
    		}
    	}
    	
    	public ListNode reverseLinkedList(ListNode head){
    		
    		if(head == null){
    			return null;
    		}
    		// 当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
    		ListNode pre = null;
    		ListNode next = null;
    		
    		// 此循环的目的就是让当前节点从指向next到指向pre
    		while(head != null){
    			// 先用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;
    	}
    }

[https_www.nowcoder.com_questionTerminal_75e878df47f24fdc9dc3e400ec6058ca]: https://www.nowcoder.com/questionTerminal/75e878df47f24fdc9dc3e400ec6058ca
[20190106174245716.png]: /images/20220330/df15cc0c61564bc18059c1863519967f.png