反转链表

楚天乐 100 0 条

算法思想

  1. 初始条件,头结点不能为null,否则直接返回null
  2. 对于第i个节点,我们只要得到第i+1到last节点的逆序链表。假设第i+1到last节点的逆序链表的最后一个元素叫prev,那我们只要把prev.next设置为当前节点,并返回当前节点即可
  3. 对于最后一个节点last,last.next是null,我们直接返回last即可
  4. 以上三步可以逆序,但我们好像没保存新的头结点(原来的尾节点),第三部保存一下即可

上代码

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    protected ListNode newHead;
    public ListNode ReverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode last = ReverseListRecursive(head);
        last.next = null;
        return newHead;
    }

    public ListNode ReverseListRecursive(ListNode node) {
        if(node.next != null){
            ListNode prev = ReverseListRecursive(node.next);
            prev.next = node;
            return node;
        }else{
            newHead = node;
            return node;
        }
    }
}

打赏

微信打赏

支付宝打赏



与本文相关的文章

发表我的评论
昵称 (必填)
邮箱 (必填)
网址
执行时间: 49.694061279297 毫秒