链表

206. 反转链表

迭代

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null && head.next == null) return head;
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}

双链表反转

迭代

class Solution {
    public DoubleNode reverseList(DoubleNode head) {
        DoubleNode prev = null;
        DoubleNode curr = head;
        while (head != null) {
            DoubleNode temp = head.next;
            head.next = prev;
            head.prev = curr;
            prev = head
            head = temp;
        }
        return prev;
    }
}

21. 合并两个有序链表

虚拟头结点

class Solution {
    public ListNode mergeTwoLists(ListNode l1,ListNode l2) {
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        ListNode p1 = l1;
        ListNode p2 = l2;
        while (p1 != null && p2 != null) {
            // 比较p1,p2的val,将较小值的节点移到p指针上
            if (p1.val > p2.val) {
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            // p指针不断前进
            p = p.next;
        } 
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return dummy.next;
    }
}