35.翻转链表

描述

翻转一个链表

样例

给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null

挑战

在原地一次翻转完成

代码

1. 迭代，时间复杂度 O(N)，空间复杂度 O(1)

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: The new head of reversed linked list.
     */

   /* null -> 1 -> 2 -> 3 -> null
    * prev   head
    * null <- 1 -> 2 —> 3 -> null
    *        prev head
    * null <- 1 <- 2 -> 3 -> null
    *             prev head
    * null <- 1 <- 2 <- 3 <- null
    *                  prev  head
    */
    // prev 和 head 保持先后顺序一步一步往右移
    // 当 head 为 null 时正好 prev 指向最后一个结点
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}

2. 递归，时间复杂度 O(N)，空间复杂度为递归所需要开辟的栈空间 O(N)

public class Solution {
    /*
     * @param head: n
     * @return: The new head of reversed linked list.
     */
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode p = reverse(head.next);
        head.next.next = head;
        // 这一步不写会形成循环链表
        head.next = null;
        
        return p;
    }
}