反转链表(面试常考,非常重要)_反转链表怎么做 面试题

题目概述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点
示例 ：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

附上leetcode链接：
点击此处进入leetcode

思路与代码

思路展现

反转链表这个题目的思路非常的巧妙，在此我们先讲迭代法：
迭代法的思路是这样的：
1:首先定义一个cur指针，开始时指向我们的头节点Head，然后开始往下遍历，cur指针的作用是为了记录我们要反转的节点.
2:其次是定义我们的prev指针，这个指针用于记录当前需要反转的节点的前驱.
3:接下来定义我们的curNext指针，这个指针用于保存下一个要反转的节点.
4:最后定义newHead指针，用于存储反转后的链表的头节点.
反转链表的核心语句一共是四步：
(1):首先我们保存下一个要反转的节点,因为我们如果不保存的话,prev的初始值为null,当执行完cur.next=prev后，此时相当于链表此时只有一个节点了，那么下一个要反转的节点就丢失了，为了避免这种情况的发生，每次反转前都需要拿curNext指针来保存下一个要反转的节点.即curNext=cur.next
(2):保存完毕后，其次是执行语句cur.next=prev,既然是反转链表，说明被反转的节点的next域存储的就是其之前的前驱节点的地址.
当然在执行cur.next=prev前还需要对curNext这个指针进行非空判断，如果为空，说明有两种情况：
情况1：说明此时链表内部只有一个节点，那么反转后还是原先的节点，所以直接将cur赋值给newHead进行返回.
情况2:说明此时cur指针已经遍历到最后一个节点了，最后一个节点就是我们反转后的新链表的头节点，那么可以直接将当前cur赋值给newHead进行返回.
(3):使用prev保存每次被反转的节点，原因是每次被反转的节点都会成为下一个被反转的节点的后继节点,为了以防下一个被反转的节点找不到他的后继节点(这个后继节点之前是下一个被反转节点在反转前的前驱节点)，所以每次都会去保存被反转的节点.
(4):反转后cur就继续往下遍历.注意此处的遍历语句为cur=curNext;并不能写成cur=cur.next.

代码示例

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode prev = null;
        ListNode newHead = null;
        if (head == null) {
            return null;
        }
        while (cur != null) {
            ListNode curNext = cur.next;
            if (curNext == null) {
                newHead = cur;
            }
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return newHead;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

总结

迭代法是最常用的一个办法，其时间复杂度为O(N）,因为最坏的情况下需要遍历一遍链表才能结束(假设链表有N个节点),空间复杂度为O(1).
当然还有一种方法是递归法，理解起来比较难，大家有兴趣可以去leetcode官方去自行查看代码和解析.