LeetCode—206—Reverse Linked List

题目

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

翻译

反转单链表

迭代方式

首先我们看一张图

在这里我们定义了三个指针。指向前一个节点的pre。指向当前节点的cur。和指向下一节点的next。pre指针初始化时候指向空指针。

之后我们让当前cur指针改向。指向pre指针。pre指针在这里的作用主要是保存上一个节点的信息。

我们让pre指针指向cur指针。cur指针指向next指针。next通过节点自身的下一个元素指向下一个元素。相当于三个指针都向前走了一步。

继续重复这个过程。让cur指针指向pre指针。pre指针指向cur指针。cur指针指向next指针。next指针通过节点自身的下一个元素指向下一个元素。

具体代码如下

// 206. Reverse Linked List
// https://leetcode.com/problems/reverse-linked-list/description/
// 时间复杂度: O(n)
// 空间复杂度: O(1)
public class Solution1 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode reverseList(ListNode head) {

        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
}

递归方式

前面非递归方式是从前面数1开始往后依次处理，而递归方式则恰恰相反，它先循环找到最后面指向的数5，然后从5开始处理依次翻转整个链表。
　　首先指针H迭代到底，如下图所示，并且设置一个新的指针作为翻转后的链表的头。由于整个链表翻转之后的头就是最后一个数，所以整个过程NewH指针一直指向存放5的地址空间。

　然后H指针逐层返回的时候依次做下图的处理，将H指向的地址赋值给H->next->next指针，并且一定要记得让H->next =NULL，也就是断开现在指针的链接，否则新的链表形成了环，下一层H->next->next赋值的时候会覆盖后续的值。

继续返回操作

返回到头

代码如下：

// 206. Reverse Linked List
// https://leetcode.com/problems/reverse-linked-list/description/
// 递归的方式反转链表
// 时间复杂度: O(n)
// 空间复杂度: O(n) 
public class Solution2 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode reverseList(ListNode head) {

        // 递归终止条件
        if(head == null|| head.next == null)
            return head;

        ListNode rhead = reverseList(head.next);

        // head->next此刻指向head后面的链表的尾节点
        // head->next->next = head把head节点放在了尾部
        head.next.next = head;
        head.next = null;

        return rhead;
    }
}