面试题16:反转链表

题目:

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

思路:

定义三个指针,分别指向当前遍历的结点pNode、它的前一个结点pPrev、它的后一个结点pNext。
1)为避免链表断开,每次遍历,先保存后一个结点pNext。如果pNext==null,证明当前结点pNode是最后一个结点,即反转链表的头节点。
2)将当前结点pNode的next指向它的前一个结点pPrev。
3)所有指针后移一位。

自述(仅自己理解):循环过程中,如果判断条件不被判断块使用,同时仅在非判断块中起作用并且非判断块的代码和判断块的代码冗余,那么判断条件无用。

  • 举例:在while条件中,我使用了pNode != null的判断条件,是因为在条件块中使用了ListNode pNext = pNode.next;
    如果我在while判断使用pNode.next != null,那么条件块没有使用到该判断,而且非条件块还需要写一段冗余代码。证明此判断条件不够精准,还需提炼。

解答:

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pReverseHead = null;
        //三个指针:前面一位,当前,下一个指针
        ListNode pPrev = null;
        ListNode pNode = head;
        while (pNode != null) {
            //保存第三个指针
            ListNode pNext = pNode.next;
            if (pNext == null) {
                pReverseHead = pNode;
            }
            //反转指针指向
            pNode.next = pPrev;
            //向后移动位置
            pPrev = pNode;
            pNode = pNext;
        }
        return pReverseHead;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目链接:面试题16 反转链表 我的思路 反转链表的基本思路就是把指向后驱的指针指向前驱 如果把指针的指向改变,无...
    贾雨村甄士隐阅读 414评论 0 0
  • 题目:输入一个链表,反转链表后,输出链表的所有元素。 思路1:用列表保存链表中的所有元素,然后将其进行反转,新建链...
    minningl阅读 235评论 0 0
  • 题目描述 输入一个链表,反转链表后,输出链表的所有元素。 代码实现 主要思路 1、首先我们需要3个结点,第一个是当...
    _minimal阅读 194评论 0 0
  • 题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。 解法:
    qmss阅读 194评论 0 0
  • 关系的建立可以高于一切,我们活在关系密织的世界里,无论你以什么样的生活方式存在,都要建立一份牢不可破的关系...
    岚升阅读 220评论 1 11