4、在链表中穿针引线

lidong / 2023-05-11 / 原文

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();
    }
}

更多问题
83 - 删除排序链表中的重复元素
86 - 分隔链表
328 - 奇偶链表
2 - 两数相加
445 - 两数相加 II

3、设立链表的虚拟头结点

203 - 移除链表元素

/**
 * 不使用 dummyHead
 */
public static ListNode removeElements1(ListNode head, int val) {
    // 1.先删除符合条件的头结点
    while (head != null && head.val == val) head = head.next;
    if (head == null) return null;

    // 2.再删除其他节点
    ListNode prev = head;
    while (prev.next != null) {
        if (prev.next.val == val) prev.next = prev.next.next;
        else prev = prev.next;
    }

    return head;
}

/**
 * 使用 dummyHead
 */
public static ListNode removeElements2(ListNode head, int val) {
    ListNode dummyHead = new ListNode(-1, head);

    ListNode prev = dummyHead;
    while (prev.next != null) {
        if (prev.next.val == val) prev.next = prev.next.next;
        else prev = prev.next;
    }

    return dummyHead.next;
}

/**
 * 递归解决问题
 */
public static ListNode removeElements3(ListNode head, int val) {
    if (head == null) return null;
    head.next = removeElements3(head.next, val);
    return head.val == val ? head.next : head;
}