当前位置：首页 > news >正文

力扣考研经典题反转链表

news 2025/6/19 17:43:07

核心思想

头插法：不断的将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;}
}