5个链表的常见操作

链表

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

    public void addTail(ListNode head, int data) {
        if (head == null) {
            return;
        }
        ListNode newNode = new ListNode(data);
        while (head.next != null) {
            head = head.next;
        }
        head.next = newNode;
    }

    public void forEach(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
}

链表反转

LeetCode206：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

    /**
     * 递归.
     * <p>
     * 1. 结束条件 head.next == null;
     * 2. 递推公式 head.next.next = head; head.next = null;
     * <p>
     * 时间复杂度：O(n)
     * 空间复杂度：O(n), 其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。
     *
     * @param head
     * @return
     */
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

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

        return newHead;
    }

    /**
     * 迭代.
     * <p>
     * 时间复杂度：0(n),其中 n 是链表的长度。需要遍历链表一次。
     * 空间复杂度：O(1)。
     *
     * @param head
     * @return
     */
    public ListNode reverse02(ListNode head) {
        ListNode pre = null;
        ListNode current = head;

        while (current != null) {
            ListNode newNode = current.next;
            current.next = pre;
            pre = current;
            current = newNode;
        }

        return pre;
    }

环路检测

LeetCode 面试题 02.08. 环路检测：给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。

    /**
     * 方法一；哈希表
     * 思路与算法：一个非常直观的思路是：我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，
     * 就可以判定链表中存在环。借助哈希表可以很方便地实现。
     * <p>
     * 时间复杂度：O(N),其中 N 为链表中节点的数目。我们恰好需要访问链表中的每一个节点。
     * 空间复杂度：O(N),其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> set = new HashSet<>();
        while (pos != null) {
            if (set.contains(pos)) {
                return pos;
            }
            set.add(pos);
            pos = pos.next;
        }

        return null;
    }

两个有序的链表合并

LeetCode 21. 合并两个有序链表：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    /**
     * 递归.
     * 1. 终止条件 l1 == null || l2 == null
     * 2. l1.next = mergeTwoLists
     * <p>
     * 时间复杂度：O(n+m),其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉l1或者l2的头结点(直到至少有一个链表为空)，
     * 函数(mergeTwoList)至多只会递归调用每个节点一次。因此时间复杂度取决于合并后的链表长度，即O(n+m)
     * 空间复杂度：O(n+m),其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于
     * 递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为O(n+m)
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }

        if (l2 == null) {
            return l1;
        }

        if (l1.data <= l2.data) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

删除链表倒数第n个结点

LeetCode 19. 删除链表的倒数第 N 个结点：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

    /**
     * 方法一：计算链表长度
     * <p>
     * 1. 获取链表长度
     * 2. 遍历链表，找到节点length-n. 该节点 current.next = current.next.next
     * <p>
     * 时间复杂度：O(L),其中L为链表长度
     * 空间复杂度：O(1)
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd01(ListNode head, int n) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode current = pre;

        int length = getListNodeLength(head);

        int subLength = length - n;

        while (subLength != 0) {
            current = current.next;
            --subLength;
        }

        current.next = current.next.next;

        return pre.next;
    }

    public static int getListNodeLength(ListNode head) {
        int length = 0;

        while (head != null) {
            ++length;
            head = head.next;
        }

        return length;
    }

    /**
     * 方法二：栈
     * 先入栈，再出栈
     * <p>
     * 时间复杂度：O(L)，L链表的长度
     * 空间复杂度：O(1)
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd02(ListNode head, int n) {
        ListNode pre = new ListNode(0, head);
        ListNode current = pre;
        Deque<ListNode> stack = new LinkedList<>();

        while (current != null) {
            stack.push(current);
            current = current.next;
        }

        while (n != 0) {
            stack.pop();
            --n;
        }
        stack.peek().next = stack.peek().next.next;
        return pre.next;
    }

    /**
     * 方法三：双指针.
     *
     * 时间复杂度：O(L),其中L是链表的长度
     * 空间复杂度：O(1)
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd03(ListNode head, int n) {

        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode start = pre;
        ListNode end = pre;

        while (n != 0) {
            start = start.next;
            n--;
        }

        while (start.next != null) {
            start = start.next;
            end = end.next;
        }
        end.next = end.next.next;

        return pre.next;
    }

求链表的中间结点

LeetCode 876. 链表中间节点：给定一个头结点为 head 的非空单链表，返回链表的中间结点。

    /**
     * 1. 求数组长度
     * 2. 取值 length/2
     * <p>
     * 时间复杂度：O(L), 其中L为链表长度。
     * 空间复杂度：O(1)
     *
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {
        int length = 0;
        ListNode current = head;
        while (current != null) {
            ++length;
            current = current.next;
        }
        current = head;
        for (int i = 0; i < length / 2; i++) {
            current = current.next;
        }
        return current;
    }

    /**
     * 快慢指针.
     * 时间复杂度：O(N)O(N)，其中 NN 是给定链表的结点数目
     * 空间复杂度：O(1)O(1)，只需要常数空间存放 slow 和 fast 两个指针
     *
     * @param head
     * @return
     */
    public ListNode middleNode02(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }