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 中没有指针的概念,所以把我文章中所说的指针在代码中当作节点就好啦。