206. 反转链表

转载自Leet Code

题目描述

反转一个单链表。

示例: >输入: 1->2->3->4->5->NULL >输出: 5->4->3->2->1->NULL

进阶: - 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

---

我的代码 (迭代)

\(T(N) = O(N)\), \(S(N) = O(1)\)

{.line-numbers}

/**
 * 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 MySolution206 
{
    public ListNode reverseList(ListNode head) 
    {
    	if (head==null||head.next==null) return head;
    	
    	ListNode prev = head; ListNode p = head.next; ListNode post = p.next;
    	prev.next = null; p.next = prev;
    	
    	while (post!=null)
    	{
    		prev = p;
    		p = post;
    		post = post.next;
    		p.next = prev;
    	}
    	return p;
    }
}

方法：递归

\(T(N) = O(N)\), \(S(N) = O(N)\)

其关键在于反向工作：假设列表的其余部分已经被反转，现在我们应该如何反转它前面的部分？ 假设列表为：

\[n_1→...→n_{k-1}→n_k→n_{k+1}→...→n_m→∅\]

设从节点nk+1到nm已经被翻转，而我们正处于nk。

\[n_1→...→n_{k-1}→n_k→n_{k+1}←...←n_m\]

我们希望nk+1的下一个节点指向nk。 因此，nk.next.next = nk。 注意边界情况：n1的下一个必须指向∅。

(在第一次触及到递归边界，即head==null或head.next==null时， p被第一次赋值为该链表的末节点，即作为新链表的头节点； 在此之后每次递归向上传递的p其实都不会再更新， 每次递归仅仅是向前退一个节点到达nk， 然后将nk+1的下一个节点指向nk、将nk的下一个节点置空为null。)

---

代码

{.line-numbers}

class Solution206 
{
    public ListNode reverseList(ListNode head) 
    {
        if (head == null || head.next == null) return head;
        
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}