leecode刷题（22）-- 反转数组
leecode刷题（22）-- 反转数组
希希里之海
发布于 2019-03-19 17:33:23
发布于 2019-03-19 17:33:23
leecode刷题（22）-- 反转数组
反转数组
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
思路：
很明显，链表问题我们要通过改变指针指向来解决问题：
首先定义 per, key, last 三个指针：
pre key last
null 1 -> 2 -> 3 -> 4 -> null让 key.next = pre :
pre key last
null <- 1 2 -> 3 -> 4 -> null再让 pre = key, key = last, last = last.next：
pre key last
null <- 1 2 -> 3 -> 4 -> null重复上述操作直到 last = null ：
pre key last
null <- 1 <- 2 <- 3 <-4 5 -> null最后让 key.next = pre 即可：
pre key last
null <- 1 <- 2 <- 3 <-4 <- 5 null返回反转后的链表，其实也就是 key。
代码如下：
/**
* 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 key = head;
ListNode last = head.next;
while(last != null) {
key.next = pre;
pre = key;
key = last;
last = last.next;
}
key.next = pre;
return key;
}
}优化：
上述代码在leecode 能通过执行，但是有个问题，就是当 head = null 时，我们设置 ListNode last = head.next 就会出错，所以先判断 head（即我们设置的 key）是否为0，再设置 last 指针，然后改变设置的指针指向，当 key = null 时，我们返回 pre 。改为下述代码。
/**
* 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 key = head;
while(key != null) {
ListNode last = key.next;
key.next = pre;
pre = key;
key = last;
}
return pre;
}
}PS：
Java 中没有指针的概念，所以把我文章中所说的指针在代码中当作节点就好啦。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-03-01 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录