链表

我有个想法，不管什么操作，先给列表加上一个dummy节点，然后统一操作。

还有一点，就是感觉操作链表，还是要多定义几个指针的，比较好操作。

203. 移除链表元素

/**
 * 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 removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while(cur!=null){
            if(cur.val == val){
                pre.next = cur.next;
            }else{
                pre = cur;   
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

206. 反转链表

利用一个temp节点

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null; 
        while(cur!=null){
           temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

利用递归去做

class Solution {
    public ListNode reverseList(ListNode head) {
        //1. 递归头  终止递归条件
        if(head == null || head.next == null) return head;
        //2. 递归体  自顶向下深入
        ListNode tail = reverseList(head.next);
        //3. 回溯    自底向上跳出
        head.next.next = head;
        head.next = null;
        return tail;
    }
}

24. 两两交换链表中的节点

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 找终止条件
        if(head==null || head.next==null){
            return head;
        }
        // 单次需要执行什么
        ListNode p = head.next;
        head.next = swapPairs(p.next);
        p.next = head;
        // 返回值
        return p;
    }
}