Leetcode 206题 反转链表(Reverse Linked List)Java语言求解

2020年1月25日21:13:58算法 LeetCode评论38阅读模式

题目描述:
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL文章源自随机的未知-https://sjdwz.com/11111.html

迭代解法

/**
Definition for singly-linked list.
public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
}
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while(head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

对代码进行解释:
1、准备两个空节pre和next点进行后续的操作,其中pre保存head之前的节点、next做临时变量;
2、如果head不空便进入循环体,转3;否则退出循环,返回pre,程序结束。
3、首先对临时变量next进行赋值,赋值为head的next值,以便操作过程中链表不断,转4;
4、为head的next赋值为pre(head的前一个元素),转5;
5、将pre赋值为当前的head的值,转6;
6、将head向后移动一位,赋值为next当前值,转2。文章源自随机的未知-https://sjdwz.com/11111.html

提交结果截图:文章源自随机的未知-https://sjdwz.com/11111.html

Leetcode 206题 反转链表(Reverse Linked List)Java语言求解
提交

递归解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
       //1.基本问题的解
        if(head == null || head.next == null){
           return head;
       }
       //2.将大问题分解成小问题
        ListNode reve = reverseList(head.next);
        //3.将小问题的解变成大问题的解
        head.next.next = head;
        head.next = null;
        return reve;
    }
}

对代码进行解释:
1、首先看递归头,也就是问题的基本问题:如果传入的是空或者只有一个节点,不用反转直接返回就可以;
2、将大问题分成小问题:就是反转head.next及其后面的节点组成的链表即可;
3、将小问题的解变成大问题的解:将原head.next的next指向head,原head的next变成空即可。
提交结果截图:文章源自随机的未知-https://sjdwz.com/11111.html

Leetcode 206题 反转链表(Reverse Linked List)Java语言求解
以上便是反转链表的迭代与递归两种解法。文章源自随机的未知-https://sjdwz.com/11111.html

欢迎关注

扫下方二维码即可关注:
Leetcode 206题 反转链表(Reverse Linked List)Java语言求解文章源自随机的未知-https://sjdwz.com/11111.html

文章源自随机的未知-https://sjdwz.com/11111.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
  • 本文由 发表于 2020年1月25日21:13:58
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11111.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定