LeetCode 206题 反转链表（Reverse Linked List）
LeetCode 206题 反转链表（Reverse Linked List）
code随笔
发布于 2020-04-14 11:32:57
发布于 2020-04-14 11:32:57
题目描述： 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
迭代解法
/**
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。
提交结果截图：
递归解法
/**
* 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变成空即可。 提交结果截图：
以上便是反转链表的迭代与递归两种解法。
欢迎关注
微信公众号:code随笔
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-01-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录