剑指Offer面试题16（Java版）：翻转链表

蔚落 2022-07-16 04:53 110阅读 0赞

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

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

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

![Center][]

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

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

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

分析写出下面的代码：

**\[java\]**  [view plain][]   [copy][view plain]

1.  /\*\* 
2.   \* 定义一个函数，输入一个链表的头结点，反转该链表并输出反转后的头结点。 
3.   \*/  
4.  **package** swordForOffer;  
5.    
6.  **import** utils.ListNode;  
7.    
8.  /\*\* 
9.   \* @author JInShuangQi 
10.  \* 
11.  \* 2015年8月1日 
12.  \*/  
13. **public** **class** E16ReverseList \{  
14.     **public** ListNode ReverseList(ListNode head)\{  
15.         **if**(head == **null**)  
16.             **return** **null**;  
17.         ListNode preListNode = **null**;  
18.         ListNode nowListNode = head;  
19.           
20.         **while**(nowListNode != **null**)\{  
21.             ListNode nextListNode = nowListNode.next;   //保存下一个结点  
22.             nowListNode.next = preListNode;             //当前结点指向前一个结点  
23.             preListNode = nowListNode;                  //前任结点 到现任节点  
24.             nowListNode = nextListNode;                 //现任节点到下一结点  
25.         \}  
26.         **return** preListNode;  
27.     \}  
28.     **public** **static** **void** main(String\[\] args)\{  
29.         ListNode head = **new** ListNode();  
30.         ListNode second = **new** ListNode();  
31.         ListNode third = **new** ListNode();  
32.         ListNode forth = **new** ListNode();  
33.         head.next = second;  
34.         second.next = third;  
35.         third.next = forth;  
36.         head.data = 1;  
37.         second.data = 2;  
38.         third.data = 3;  
39.         forth.data = 4;  
40.         E16ReverseList test = **new** E16ReverseList();  
41.         ListNode result = test.ReverseList(head);  
42.         System.out.println(result.data);  
43.     \}  
44. \}

[Center]: /images/20220716/bcf180f0cd424466b9ebc2478be07b72.png
[view plain]: http://blog.csdn.net/jsqfengbao/article/details/47187709#