做网站的专业,网站后台管理代码,男女做暖暖的试看网站,响应式网页设计总结核心思想
头插法#xff1a; 不断的将cur指针所指向的节点放到头节点之前#xff0c;然后头节点指向cur节点#xff0c;因为最后返回的是head.next 。
解题思路
1.如果头节点是空的#xff0c;或者是只有一个节点#xff0c;只需要返回head节点即可。
if (head null …
核心思想
头插法 不断的将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;}
}
图解 头插法的好处
不需要额外的空间存储反转后的链表,操作都在原链表上进行。时间复杂度为O(n),只需要遍历链表一次。代码实现相对简单,逻辑清晰,易于理解和实现。
