LinkedList

1. 打印两个有序链表的公共部分

节点一定要注意null

public void printCommonPart(Node head1, Node head2) {
    while (head1 != null && head2 != null) {
        if (head1.value < head2.value) {
            head1 = head1.next;
        } else if (head1.value > head2.value) {
            head2 = head2.next;
        } else {
            System.out.print(head1.value + " ");
            head1 = head1.next;
            head2 = head2.next;
        }
    }
}

2.在单链表和双链表中删除倒数第k个节点

time=n，space=1
如果链表长度为N，要删除倒数第k个节点，倒数第k个节点的前一个节点就是第N-K个节点。
在第一次遍历后，K的值变为K-N。第二次遍历时，K的值不断加1，加到0就停止遍历，第二次遍历当然会停到第N-K个节点的位置。

public Node removeLastKthNode(Node head, int lastKth) {
    if (head == null || lastKth < 1) {
        return head;
    }
    Node cur = head;
    while (cur != null) {
        lastKth--;
        cur = cur.next;
    }
    if (lastKth == 0) {
        return head.next;
    }
    if (lastKth < 0) {
        cur = head;
        while (++lastKth < 0) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
    }
    return head;
}

public DoubleNode removeLastKthNode(DoubleNode head, int lastKth) {
    if (head == null || lastKth < 1) {
        return head;
    }
    DoubleNode cur = head;
    while (cur != null) {
        lastKth--;
        cur = cur.next;
    }
    if (lastKth == 0) {
        head = head.next;
        head.last = null;
    }
    if (lastKth < 0) {
        cur = head;
        while (++lastKth != 0) {
            cur = cur.next;
        }
        DoubleNode newNext = cur.next.next;
        cur.next = newNext;
        // 防止忘记判断链表末尾的情况
        if (newNext != null) {
            newNext.last = cur;
        }
    }
    return head;
}

3.删除链表的中间节点

快指针和慢指针一起移动，慢指针即为中间点，但是想要找慢指针前一个节点，只需要快指针先移动一步，快慢指针再一起移动，快指针停止时，慢指针指向节点即为中间节点的前一个节点

public Node removeMiddleNode(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    if (head.next.next == null) {
        return head.next;
    }
    Node pre = head;
    // 要找中间节点前一个节点需要快指针先行移动一步
    Node cur = head.next.next;
    while (cur.next != null && cur.next.next != null) {
        pre = pre.next;
        cur = cur.next.next;
    }
    pre.next = pre.next.next;
    return head;
}

4.反转单向和双向链表

time n ,space 1

public Node reverseSingleLinkedList(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    Node pre = null;
    Node cur = null;
    while (head != null) {
        cur = head;
        head = head.next;
        cur.next = pre;
        pre = cur;
    }
    return cur;
}

public DoubleNode reverseDoubleLinkedList(DoubleNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    DoubleNode pre = null;
    DoubleNode cur = null;
    while (head != null) {
        cur = head;
        head = head.next;
        cur.next = pre;
        cur.last = head;
        pre = cur;
    }
    return cur;
}

5. 反转部分单向链表

public Node reversePart(Node head, int from, int to) {
    int len = 0;
    Node n1 = head;
    Node fPre = null;
    Node tPos = null;
    while (n1 != null) {
        len++;
        fPre = len == from - 1 ? n1 : fPre;
        tPos = len == to + 1 ? n1 : tPos;
        n1 = n1.next;
    }
    if (from > to || from < 1 || to > len) {
        return head;
    }
    n1 = fPre == null ? head : fPre.next;
    Node n2 = n1.next;
    n1.next = tPos;
    Node next;
    while (n2 != tPos) {
        next = n2.next;
        n2.next = n1;
        n1 = n2;
        n2 = next;
    }
    if (fPre != null) {
        fPre.next = n1;
        return head;
    }
    return n1;
}

判断一个链表是否为回文结构

• 方法一：时间复杂度为N，利用栈，空间复杂度为N ，难度一星。

public boolean isPalindrome1(Node head) {
        Stack<Integer> stack = new Stack<>();
        Node cur = head;
        while (cur != null) {
            stack.push(cur.value);
            cur = cur.next;
        }
        
        while (!stack.isEmpty()) {
            if (stack.pop() != head.value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

两个单链表生成相加链表

方法一：需要额外栈空间

public Node addList1(Node head1, Node head2) {
    int n1 = 0;
    while (head1 != null) {
        n1 = n1 * 10 + head1.value;
        head1 = head1.next;
    }
    int n2 = 0;
    while (head2 != null) {
        n2 = n2 * 10 + head2.value;
        head2 = head2.next;
    }
    int n = n1 + n2;
    Stack<Integer> stack = new Stack<>();
    while (n > 0) {
        stack.push(n % 10);
        n /= 10;
    }

    Node head = new Node(stack.pop());
    Node cur = head;
    while (!stack.isEmpty()) {
        cur.next = new Node(stack.pop());
        cur = cur.next;
    }
    return head;
}

在单链表中删除指定值的节点

方法一：需要申请额外set数据结构，空间复杂度n

public void removeRep1(Node head) {
    if (head == null) {
        return;
    }
    HashSet<Integer> set = new HashSet<>();
    Node pre = head;
    Node cur = head.next;
    set.add(head.value);
    while (cur != null) {
        if (set.contains(cur.value)) {
            pre.next = cur.next;
        } else {
            set.add(cur.value);
            pre = cur;
        }
        cur = cur.next;
    }
}

public Node removeValue1(Node head, int num) {
    // 加头结点
    Node first = new Node(0);
    first.next = head;
    Node pre = first;
    Node cur = head;
    while (cur != null) {
        if (cur.value == num) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return first.next;
}

单链表的选择排序

要求：额外空间复杂度O（1）

public Node selectionSort(Node head) {
    Node cur = head;
    Node tail = null;
    Node minPre;
    Node min;
    while (cur != null) {
        minPre = getMinPreNode(cur);
        if (minPre == null) {
            min = cur;
        } else {
            min = minPre.next;
            minPre.next = min.next;
        }
        cur = cur == min ? cur.next : cur;

        if (tail == null) {
            head = min;
        } else {
            tail.next = min;
        }
        tail = min;
    }
    return head;
}

public Node getMinPreNode(Node head) {
    Node minPre = null;
    Node min = head;
    Node pre = head;
    Node cur = head.next;

    while (cur != null) {
        if (cur.value < min.value) {
            minPre = pre;
            min = cur;
        }
        pre = cur;
        cur = cur.next;
    }
    return minPre;
}

一种怪异的节点删除方式

要求：时间复杂度为O(1)

public void removeNodeWeird(Node node) {
    Node next = node.next;
    if (next == null) {
        node = null;
        return;
    }
    node.value = next.value;
    node.next = next.next;
}

向有序的环形链表中插入新节点

time n,space 1

public Node insertNum(Node head, int num) {
    if (head == null) {
        return new Node(num);
    }
    Node cur = head;
    Node node = new Node(num);
    while (true) {
        boolean ins = cur.value <= num && num <= cur.next.value || cur.value > cur.next.value;
        if (ins) {
            node.next = cur.next;
            cur.next = node;
            if (num < head.value) {
                return node;
            }
            return head;
        }
        cur = cur.next;
    }
}

合并两个有序的单链表

time M+N，space 1

public Node merge(Node head1, Node head2) {
    Node first = new Node(0);
    Node p1 = head1;
    Node p2 = head2;
    Node p = first;
    while (p1 != null && p2 != null) {
        if (p1.value <= p2.value) {
            p.next = p1;
            p1 = p1.next;
        } else {
            p.next = p2;
            p2 = p2.next;
        }
        p = p.next;
    }
    while (p1 != null) {
        p.next = p1;
        p1 = p1.next;
        p = p.next;
    }
    while (p2 != null) {
        p.next = p2;
        p2 = p2.next;
        p = p.next;
    }
    return first.next;
}

按照左右半区的方式重新组合单链表

time n，space 1
代码按功能拆分成多个方法

public void relocate(Node head) {
    if (head == null || head.next == null) {
        return;
    }
    Node mid = head;
    Node right = head.next;
    while (right.next != null && right.next.next != null) {
        mid = mid.next;
        right = right.next.next;
    }
    right = mid.next;
    mid.next = null;
    mergeLR(head, right);
}

public void mergeLR(Node left, Node right) {
    Node next;
    while (left.next != null) {
        next = right.next;
        right.next = left.next;
        left.next = right;
        left = right.next;
        right = next;
    }
    left.next = right;
}