链表反转是链表算法题中较为基础的一道题,但对于初学者来说,由于对链表的结构不是很熟悉,一时间无从下手,甚至看别的的阶梯代码都会觉得很晕,看不懂一堆变量都是做什么的。我将会详细描述链表反转的操作,希望对这些小伙伴有一点帮助。力扣链接
我们要反转一个链表,只需更改每个节点的指向,让其指向前一个节点,让第一个节点指向null作为尾结点。由于单向链表无法直接获取到前一个节点的引用,所以我们可以在一开始用prev表示第一个节点,用cur表示第二个节点,每次让cur.next=prev,然后prev和cur一起向后遍历即可,但我们已经更改了cur的next的指向,也就丢失了cur后面所有的节点,因此,我们需要在更改cur.next之前先用nextNode拷贝一份cur.next,待cur中next被更改之后,让cur=nextNode即可遍历到后面的节点,然后循环更改指向即可。
需要注意的是:循环开始时和循环结束时需要专门处理,头结点再反转后成为了尾结点,所以应该指向null。在循环结束时,nextNode为null,此时的cur为最后一个节点,由于循环退出,没能将cur.next做出修改,需专门处理,最后还应该将head=cur。当传入的head为null,或者是只有一个节点时,需要特别处理。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if(head==null){return null;}if(head.next==null){return head;}ListNode cur=head.next;head.next=null;ListNode prev=head;ListNode nextNode=null;while(cur.next!=null){nextNode=cur.next;cur.next=prev;prev=cur;cur=nextNode;}cur.next=prev;return cur;}
}