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