反转一个单链表(Java)

反转一个单链表(Java),第1张

看到反转链表,可能第一时间的想法便是遍历一遍这个单链表,然后把链表里的元素都取出来,放到一个数组里,然后逆置这个数组。这个想法是错的!!!

所以什么是反转链表呢?见下图:

 

反转一个单链表,我们需要的是改变这个链表内节点的指向。

反转链表第一步:

判断链表是否为空,如果链表为空,则直接返回null。

if (this.head == null) {    //没有节点
            return null;
        }

反转链表第二步:

判断链表是否只有一个节点,如果头结点的下一节点等于空,则说明该链表只有一个节点,即返回头结点。

  if (this.head.next == null) {   //只有一个节点
            return this.head;
        }

反转链表第三步:

//至少两个节点 
Node cur=this.head.next;
 this.head.next=null;
 while (cur!=null){
     Node curNext=cur.next;
     cur.next=head;
     this.head=cur;
     cur=curNext;
 }
   return head;

第三步详解如下:

链表反转后,它原本的头结点的下一节点就为空null了。但是不能在一开始就将头结点的下一节点置为空。因为将它置为空后,便失去了与链表本来head.next的联系;所以,我们定义一个cur记录头结点下一节点的位置;也就是说让head不动,将记录头结点下一节点位置的cur用头插法的方式插入到head的前边,在cur头插到head前再定义一个curNext记录cur的下一节点,使cur到了head前,也不会失去与后边节点的联系。当所有的链表都反转后,cur就会为空。

图解

 

 

 

 

 

完整代码如下:

 class Node{
    public int val;
    public Node next;  //类型是Node          null

    public Node(int val){
        this.val=val;

    }
} 

public class SingleLinkedList {
    public Node head;

 //反转链表
    //反转链表并不能使用逆置数组,需要改变链表元素的指向(使用头插法)
    public Node reverseList() {
        if (this.head == null) {    //没有节点
            return null;
        }
        if (this.head.next == null) {   //只有一个节点
            return this.head;
        }
        //至少有两个节点
        Node cur=this.head.next;
        this.head.next=null;
        while (cur!=null){
            Node curNext=cur.next;
            cur.next=head;
            this.head=cur;
            cur=curNext;
        }
        return head;
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: https://www.outofmemory.cn/langs/723383.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-26
下一篇 2022-04-26

发表评论

登录后才能评论

评论列表(0条)

保存