leecode刷题(22)-- 反转数组

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

上一篇:数字签名(Open SSL)


下一篇:LeeCode第一次刷题(两数相加)