Recursive List 类题目的解法

举个栗子：

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

1	Given 1->2->3->4, you should return the list as 2->1->4->3.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null) return null;
        return swap(head);
    }
    
    public ListNode swap(ListNode n){
        if(n == null || n.next == null) return n;
        ListNode node = n.next;
        n.next = swap(node.next);
        node.next = n;
        return node;
    }
}

像这道题里需要交换顺序，那么recursive应该怎么设计？

首先观察顺序分组

1 2	2->1 是一组 4->3 是一组

然后从 1又连接到4

那么显而易见在一步recursion里要完成什么步骤

1. 送进来的应该是第一个node
2. 读取第二个node
3. 第一个node的next设为下一个组的头（这里进入recursion）（所以如果我们的代码正确就不用关心返回什么了 因为肯定是下一组的头）
4. 将第二个node的next设为第一个node
5. 返回第二个node(非常重要 因为他是新的头)

简而言之，一道list的recursion题最重要的点就是关心 1. 送进来的是哪个node 2.返回去的是哪个node 以及在这一组操作之间要完成哪些步骤。只要这三个对了整个recursion就是对的

另外作为recursion，我们同样要关心base case，也就是整个循环结束的条件

因为像这题如果list的elements是单数，那么最后就会剩下一个，而它不会有next了，所以结束条件为了不出错肯定要 n == null || n.next == null 为结束条件。那么还有一个东西很关键，当结束条件满足时应该返回什么？根据前面的叙述显而易见，应该返回那个单数本身，所以应该是return n 。这样一道recursive node 题就解出来了。

# List, Recursive

Recursive List 类题目的解法

Categories

Tag Cloud

Archives

Tags

Your browser is out-of-date!