LeetCode 206. Reverse Linked List

Problem

LeetCode 206. Reverse Linked List

1. 题目简述

给出一个链表，翻转该链表。例如：

Example:

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

2. 算法思路

最经典的题目之一了，没啥好说的，背就完了，其进阶版本LeetCode 92. Reverse Linked List II。

自己画图，找出ptr，pre和post之间的连接关系应该怎么去解决，以及边界条件，初始化的问题，稍微注意一下就好，难是不难，就是绕。

for循环

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode ptr = head, pre = null;

        while (ptr != null) {
            ListNode post = ptr.next;
            // 将后面指向前面，第一个元素反转后将会是末尾，所以指向null，没毛病
            ptr.next = pre;
            pre = ptr;
            ptr = post;
        }

        return pre;
    }
}

递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode reversed = reverseList(head.next);
        //这时候，head.next被置换到了末尾，所以需要将末尾指向自己
        head.next.next = head;
        // 注意置换到了末尾后，要将自己的next置为null
        head.next = null;

        return reversed;
    }
}