4、在链表中穿针引线

1、反转链表

206 - 反转链表

/**
 * 非递归实现
 * 最终状态如下
 * cur、next -> null
 * prev -> newHead
 */
public static ListNode reverseList1(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;
    ListNode next;
    while (cur != null) {
        next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }

    return prev;
}

/**
 * 递归: 反转以 head 为头的链表, 并返回新的头结点
 */
public static ListNode reverseList2(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode newHead = reverseList2(head.next);
    head.next.next = head;
    head.next = null;

    return newHead;
}

更多问题
92 - 反转链表 II

2、测试你的链表程序

public class ListNode {

    public int val;
    public ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this(val, null);
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public ListNode(int[] arr) {
        if (arr == null || arr.length == 0) throw new IllegalArgumentException("Arr is empty.");

        this.val = arr[0];
        ListNode cur = this;
        for (int i = 1; i < arr.length; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        ListNode cur = this;
        while (cur != null) {
            sb.append(cur.val).append("->");
            cur = cur.next;
        }
        sb.append("NULL");
        return sb.toString();
    }
}

3、删除排序链表中的重复元素

83 - 删除排序链表中的重复元素