力扣考研经典题 反转链表

核心思想

头插法： 不断的将cur指针所指向的节点放到头节点之前，然后头节点指向cur节点，因为最后返回的是head.next 。

解题思路

1.如果头节点是空的，或者是只有一个节点，只需要返回head节点即可。

if (head == null || head.next == null) return head;

2.定义一个cur节点，我们要做的就是不断的把cur节点头插到head节点。head.next置为空。我们只要在这个链表上操作。实际上就是断开成两条链表，cur指针在另一个链表上不断的遍历，而另一个就是我们要的head

ListNode cur = head.next;
head.next = null;

3.头插法操作，我们需要一个curNext来保存cur的下一个节点。因为cur一直要用来头插，而这时候就会断链 ，导致不知道cur的下一个节点在哪里，因此用一个指针来记录。

   while (cur != null) {
            ListNode curNext = cur.next;
            //需要记录cur节点的下一个节点，因为每次都是cur节点插到头节点前面
            //下次使用的时候必须能找到cur的下一个节点，因为curNext是下一次头插的节点
            cur.next = head;
            head = cur;
            //上述就是头插法
            cur = curNext;
        }

完整代码

 

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode cur = head.next;
        head.next = null;
        //在这里需要断开头节点和后面的节点，然后进行头插法
        while (cur != null) {
            ListNode curNext = cur.next;
            //需要记录cur节点的下一个节点，因为每次都是cur节点插到头节点前面
            //下次使用的时候必须能找到cur的下一个节点，因为curNext是下一次头插的节点
            cur.next = head;
            head = cur;
            //上述就是头插法
            cur = curNext;
        }
        return head;
    }
}

图解

 

 

 

 

 

 

 

 

 

 

 

头插法的好处

1. 不需要额外的空间存储反转后的链表,操作都在原链表上进行。
2. 时间复杂度为O(n),只需要遍历链表一次。
3. 代码实现相对简单,逻辑清晰,易于理解和实现。