反转链表

xiaoxiao2021-03-01  33

题目描述

输入一个链表,输出该链表中倒数第k个结点。

思路分析:

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

        不难注意,由于结点i的next指向了它的前一个结点,导致我们无法在链表中遍历到结点j。为了避免在链表i处断开,我们需要调整结点i的next之前,把结点j保存下来。也就是说,我们在调整i的next时,除了需要知道当前结点本身之外,还需要i的前一个结点h(因为我们需要把i的next指向h),同时还需要保存i的下一个结点j,以防止链表断开。所以我们需要相应的定义3个指针:分别指向当前遍历的结点、它的前一个结点和后一个结点。

        最后我们需要找到反转后的链表的头结点,不难分析,反转后的链表的头结点是原始链表的尾结点,也就是next为空的结点。

注意:

要注意代码的鲁棒性,也就是对特殊值的处理,即当链表为空指针、链表只有一个结点的时候。此外还需要注意防止反转后的链表断裂,或者反转后的头结点不是原始链表的尾结点。

Java实现:

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode ReverseList(ListNode head) { ListNode ReverseHead=null; ListNode pNode=head; ListNode pPrev=null; while(pNode!=null){ ListNode pNext=pNode.next; //如果pNext为空,则pNode必为原链表的尾结点,也就是反转后的链表的头结点 if(pNext==null) ReverseHead=pNode; pNode.next=pPrev; pPrev=pNode; pNode=pNext; } return ReverseHead; } }
转载请注明原文地址: https://www.6miu.com/read-3199984.html

最新回复(0)