剑指offer面试题[16]-反转链表

不念不忘少年蓝@ 2022-06-13 06:27 195阅读 0赞

## 题目描述 ##

输入一个链表，反转链表后，输出链表的所有元素。

解决与链表相关的问题总是有大量的指针操作，而指针操作的代码总是容易出错的的。很多面试官喜欢出链表相关的问题，就是想通过指针操作来考查应聘者的编码功底。为了避免出错，我们最好先进行全面的分析。

**  在实际软件开发周期中，设计的时间通常不会比编码的时间短**。在面试的时候我们不要急于动手写代码，而是一开始仔细分析和设计，这将会给面试官留下很好的印象。与其很快写出一段漏洞百出的代码，倒不如仔细分析再写出鲁棒性的代码。

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

![7491640_1498741606779_7090821EEB0F20C6B805DC8DA0ED8914][]           ![Image 1][]

注：图1-（a）一个链表。图1-（b）把i之前所有的结点的next都指向前一个结点，**导致链表在结点i、j之间断裂**。

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

也就是说我们在调整结点i的next指针时，除了要知道结点i本身之外，还需要知道i的前一个结点h，因为我们要把结点i的next指向结点h。同时，我么需要保存i的下一个结点j，以防止链表断开。

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

代码如下：

/\*  
struct ListNode \{  
int val;  
struct ListNode \*next;  
ListNode(int x) :  
val(x), next(NULL) \{  
\}  
\};\*/  
class Solution \{  
public:  
    ListNode\* ReverseList(ListNode\* pHead) \{  
        ListNode\* pPnode=pHead;                   //当前结点  
        ListNode\* pPre=NULL;                         //定义当前结点的前一个结点  
        ListNode\* pReverseHead=NULL;         //反转链表的头结点  
        while(pPnode!=NULL)  
            \{  
               ListNode\* pNext=pPnode->next;    //用临时结点pNext来保存当前结点的下一个结点  
               if(pNext==NULL)                            //当前结点的next为空时，说明已经到了最后一个结点，此时需要将当前结点作为反转链表的头结点  
                     pReverseHead=pPnode;    
               pPnode->next=pPre;                     //这里三行代码意思是在更新当前结点，前一个结点等，结合图形分析比较好理解  
               pPre=pPnode;  
               pPnode=pNext;  
            \}  
        return  pReverseHead;  
    \}  
\};

[7491640_1498741606779_7090821EEB0F20C6B805DC8DA0ED8914]: https://uploadfiles.nowcoder.com/images/20170629/7491640_1498741606779_7090821EEB0F20C6B805DC8DA0ED8914
[Image 1]: