欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【剑指Offer-Java】反转链表

程序员文章站 2022-07-10 13:58:27
...

反转链表

题目描述

输入一个链表,反转链表后,输出新链表的表头。

思路

定义个前驱结点pre和后继节点next
先用next保存head的下一个结点的信息,保证链表不会因为失去head结点的原next结点而断裂!!!
开始反转:把head转向next,变成指向pre。再将pre,head,next都向后移动一步,继续下一次的指针反转
最后反转结束后,即head为null时,此时pre成为了最后一个结点,也就是反转链表的头结点,所以直接返回pre

实现

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //特殊情况:链表为空
        if(head==null) return null;
        //定义前驱结点和后继节点
        ListNode pre=null;
        ListNode next=null;
        //遍历链表过程中反转链表
        while(head!=null){
            //先用next保存下一个结点的信息,保证链表不会因为失去head结点的原next结点而断裂
            next=head.next;
            //保存好结点信息就可以开始反转了
            //把head转向next,变成指向pre
            head.next=pre;
            //再将pre,head,next都向后移动一步,继续下一次的指针反转
            pre=head;
            head=next;
        }
        //反转结束后,即head为null时,此时pre成为了最后一个结点,也就是反转链表的头结点,所以直接返回pre
        return pre;
    }
}