链表

1、从尾到头打印链表

public class T3 {
    // 创建list
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        // 判断头节点是否为空
        if (listNode != null) {
            // 递归打印
            this.printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
}

2、删除链表中重复的结点

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

public ListNode deleteDuplication(ListNode pHead) {
    // 1. 边界，需要下一个结点做判断，因此还是需要判断下个结点是否为空
    if (pHead == null || pHead.next == null)
        return pHead;
    // 取下一个结点
    ListNode next = pHead.next;
    // 2. 判断当前结点和下一个结点是否相等
    if (pHead.val == next.val) {
        // 3. 如果相等，判断是否一直重复
        while (next != null && pHead.val == next.val)
            next = next.next;
        return deleteDuplication(next);
    } else {
        // 4， 否则不重复的话，就递归下一个结点
        pHead.next = deleteDuplication(pHead.next);
        return pHead;
    }
}

3.1 环形链表

https://leetcode-cn.com/problems/linked-list-cycle/

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode l1 = head, l2 = head.next;
        while (l1 != null && l2 != null && l2.next != null) {
            if (l1 == l2) {
                return true;
            }
            l1 = l1.next;
            l2 = l2.next.next;
        }
        return false;
    }
}

3.2、链表中环的入口结点

https://leetcode-cn.com/problems/linked-list-cycle-ii/submissions/

// 快慢指针
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null)
            return null;
        
        boolean hasCycle = false;
        ListNode p1 = head, p2 = head;
        while(p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {
                hasCycle = true;
                break;
            }
        }
        if(hasCycle){
            p2 = head;
            while (p1 != p2) {
                p1 = p1.next;
                p2 = p2.next;
            }
            return p1;
        } else {
            return null;
        }
    
    }
}

4、反转链表

https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

public ListNode reverseList(ListNode head) {
    // 总感觉，本质还是两个指针，pre不过初始化为null，cur为head当前结点
    ListNode pre = null; 
    ListNode cur = head;
    while (cur != null) {
        // 1. 获取当前节点的下一个节点，方便cur下移动
        ListNode nextTemp = cur.next;
        // 2. 当前节点的下个节点指向前一个节点 （反转，那肯定cur的next指向pre咯）
        cur.next = pre; 
        // 3. pre移动下一个结点，那肯定是cur咯
        pre = cur; 
        // 4. cur移动下一个结点， 那肯定是nextTemp咯
        cur = nextTemp;
    }
    return pre;
}
public class T15 {
    public ListNode ReverseList(ListNode head) {
        // 判断
        if (head == null) return null;
        return reverse(null, head);
    }
    private ListNode reverse(ListNode pre, ListNode cur) {
        // 递归结束判断
        if (cur == null) return pre;
        // 1. 依然第一个方法遍历依然，得到cur的next，递归用
        ListNode next = cur.next;
        // 2. 反转操作
        cur.next = pre;
        return reverse(cur, next);
    }
}

5、链表中倒数第k个结点

https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

public ListNode FindKthToTail(ListNode head, int k) {
    // 还是双指针
    // 1. 边界判断
    if (head == null)
        return null;
    ListNode p1 = head;
    // 2. 先让p1移动k步
    while (p1 != null && k-- > 0)
        p1 = p1.next;
    // 3. 这一步防止k大于head的长度
    if (k > 0)
        return null;
    ListNode p2 = head;
    // 4. 二者正常走，不过p1肯定先到末尾
    while (p1 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    // 5. 返回p2
    return p2;
}

6、合并两个排序的链表

https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

public class T16 {
    public ListNode Merge(ListNode list1,ListNode list2) {
        // 1. 如果list1为空，返回list2
        if (list1 == null) return list2;
        // 2. 如果list2为空，返回list1
        if (list2 == null) return list1;
        // 3. 如果list1.val < list2.val，则list1.next连接下一个比较值（递归比较）
        if (list1.val < list2.val) {
            list1.next = Merge(list1.next, list2);
            return list1;
        } else {
            // 4. 否则，list2.next 连接下一个比较值（递归比较）
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }
}

7、两个链表的第一个公共结点

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

// 还是双指针
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    ListNode l1 = pHead1, l2 = pHead2;
    // 1. 循环条件
    while (l1 != l2) {
        // 2. 走完l1，从头走head2
        l1 = (l1 == null) ? pHead2 : l1.next;
        // 3. 走完l2，从头走head1
        l2 = (l2 == null) ? pHead1 : l2.next;
    }
    // 4. 返回l1
    return l1;
}

8. 两数相加(2819)

https://leetcode-cn.com/problems/add-two-numbers/

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 边界判断：3个
        // 1. l1和l2同时为空
        if (l1 == null && l2 == null) return null;
        // 2. l1为空，返回l2
        if (l1 == null) return l2;
        // 3. l2为空，返回l1
        if (l2 == null) return l1;
        // 三指针
        // 1. p1
        ListNode p1 = l1;
        // 2. p2
        ListNode p2 = l2;
        // 3. p3 特殊：返回最值链表
        ListNode l3 = new ListNode(-1);
        ListNode p3 = l3;
        // 4. 注意：进位
        int carried = 0;
        // 5. 循环条件，任意一个不为空即可
        while (p1 != null || p2 != null) {
            // p1不为空，获取p1val，否则0
            int a = p1 != null ? p1.val : 0;
            // p2不为空，获取p2val，否则0
            int b = p2 != null ? p2.val : 0;
            // 关键一步，(a+b+carried) % 10 个位
            p3.next = new ListNode((a + b + carried) % 10);
            // 加完，记得进位呀(a + b + carried) / 10
            carried = (a + b + carried) / 10;
            // 三个指针开始移动
            p3 = p3.next;
            p1 = p1 != null ? p1.next : null;
            p2 = p2 != null ? p2.next : null;
        }
        // 循环完之后，判断进位是否0，如果不是，new一个结点为1，是的话，就null
        p3.next = carried != 0 ? new ListNode(1) : null;
        // 返回l3下一个结点
        return l3.next;
    }
}

9. 合并K个排序链表(924)

https://leetcode-cn.com/problems/merge-k-sorted-lists/

最小堆

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 边界判断
        if (lists == null || lists.length == 0) return null;
        // 2. 堆，大顶堆
        PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        // 3. 返回结点
        ListNode dummy = new ListNode(0);
        // 4. 临时p
        ListNode p = dummy;
        // 5. 遍历k个lists，一个一个添加到queue
        for (ListNode node : lists) {
            if (node != null) queue.add(node);
        }
        // 6. 循环堆不为空
        while (!queue.isEmpty()) {
            // p的下个结点指向 取出堆中最大的链表结点
            p.next = queue.poll();
            // 移动
            p = p.next;
            // 如果下一个不为空，继续添加刚才堆中最大的下一个结点
            if (p.next != null) queue.add(p.next);
        }
        // 7. 返回下一个结点
        return dummy.next;
    }   
}
class Solution {
   public ListNode mergeKLists(ListNode[] lists) {
        // 归并
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        // 归并排序一样
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }
    // 不过，最后归并的时候用的是合并两个排序的链表
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

10. 两两交换链表中的节点(947)

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

class Solution {
    // 两两交换，那么双指针
    public ListNode swapPairs(ListNode head) {
        // 创建一个返回结点
        ListNode node = new ListNode(-1);
        // 该结点的next指向head
        node.next = head;
        // 在创建一个pre，移动到node
        ListNode pre = node;
        // 循环遍历
        // pre的next才是head，因此判断next next
        while (pre.next != null && pre.next.next != null) {
            // 获取l1， l2
            ListNode l1 = pre.next, l2 = pre.next.next;
            // 
            ListNode next = l2.next;
            l1.next = next;
            l2.next = l1;
            pre.next = l2;
            // pre移动一步
            pre = l1;
        }
        return node.next;
    }
}

11. 链表的中间结点(853)

https://leetcode-cn.com/problems/middle-of-the-linked-list/

// 双指针（快慢）
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode p = head, q = head;
        while (q != null && q.next != null) {
            q = q.next.next;
            p = p.next;
        }
        return p;
    }
}

12. 删除排序链表中的重复元素(603)

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

// 和那个有点区别
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        head.next = deleteDuplicates(head.next);
        return head.val == head.next.val ? head.next : head;
    }
}

13. 回文链表(624)

https://leetcode-cn.com/problems/palindrome-linked-list/

这题考察了很多链表的题，挺综合额

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        // 找中点
        ListNode slow = head, fast = head.next;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 奇偶情况
        if(fast != null) slow = slow.next;
        // cut
        cut(head, slow);
        // 比较
        return isEqual(head, reverse(slow));
        
    }
    
    // 切
    public void cut (ListNode head, ListNode cutNode) {
        ListNode node = head;
        // 循环遍历找到和cutNode相等的结点的前一个结点
        while(node.next != cutNode) {
            node = node.next;
        }
        // 然后直接null
        node.next = null;
    }
    
    // 反转链表派上用场
    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode nextNode = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nextNode;
        }
        return pre;
    }
    
    
    public boolean isEqual(ListNode l1, ListNode l2) {
        // 二者都不为空才行
        while(l1 != null && l2 != null) {
            // 二者值不相等直接false
            if(l1.val != l2.val) return false;
            // 移动
            l1 = l1.next;
            l2 = l2.next;
        }
        // 比如就true
        return true;
    }
}

14. 奇偶链表(317)

https://leetcode-cn.com/problems/odd-even-linked-list/

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) return head;
        // 临时变量 奇头 偶头下 偶头部
        ListNode odd = head, even = head.next, evenHead = even;
        // 循环遍历偶和偶下不为空
        while (even != null && even.next != null) {
            // 奇 -> 奇下下
            odd.next = odd.next.next;
            // 奇移动一步
            odd = odd.next;
            // 偶 -> 偶下下
            even.next = even.next.next;
            // 偶移动
            even = even.next;
        }
        // 奇 -> 偶头
        odd.next = evenHead;
        // 返回head
        return head;
    }
}

92. 反转链表 II

https://leetcode-cn.com/problems/reverse-linked-list-ii/

/**
 * 定位到要反转部分的头节点 2，head = 2；前驱结点 1，pre = 1；
 * 当前节点的下一个节点3调整为前驱节点的下一个节点 1->3->2->4->5,
 * 当前结点仍为2， 前驱结点依然是1，重复上一步操作。。。
 * 1->4->3->2->5.
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy, cur, next;
        for (int i = 1; i < m; i++) 
            pre = pre.next;
        cur  = pre.next;
        for (int i = m; i < n; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }
}
// 投机取巧 缓存
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode p = head;
        int idx = 1;
        Stack<Integer> stack = new Stack<>();
        while (p != null) {
            if (idx >= m && idx <= n)
                stack.push(p.val);
            idx++;
            p = p.next;
        }
        idx = 1;
        p = head;
        while (p != null) {
            if (idx >= m && idx <= n)
                p.val = stack.pop();
            idx++;
            p = p.next;
        }
        return head;
    }
}

15. K 个一组翻转链表(字节爱考)

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0), pre = dummy, curr = head, next;
        // 临时赋值
        dummy.next = head;
        // 算长度
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        // 从头
        head = dummy.next;
        // 两重for遍历
        for (int i = 0; i < len / k; i++) {
            for (int j = 0; j < k - 1; j++) {
                // 谜一般的操作
                // 临时next
                next = curr.next;
                // 我指向你
                curr.next = next.next;
                // 你指向他
                next.next = pre.next;
                // 他指向临时
                pre.next = next;
            }
            pre = curr; // 移动
            curr = pre.next; // 移动
        }
        return dummy.next;
    }
}

16. 奇数位升序偶数位降序的链表

public static ListNode oddEvenLinkedList(ListNode head) {
    // 将偶数链表拆分出来
    ListNode evenHead = getEvenList(head);
    // 逆序偶数链表
    ListNode reEvenHead = reverseList(evenHead);
    // 归并奇偶链表
    ListNode mHead = mergeList(head, reEvenHead);
    return mHead;
} 

public static ListNode getEvenList(ListNode head) {
    ListNode odd = new ListNode(-1);
    ListNode even = new ListNode(-1);
    int cnt = 1;
    ListNode cur1 = odd, cur2 = even;
    while (head != null) {
        if (cnt % 2 != 0) {
            cur1.next = head;
            cur1 = cur1.next;
        } else {
            cur2.next = head;
            cur2 = cur2.next;
        }
        head = head.next;
        cnt++;
    }
    cur1.next = null;
    cur2.next = null;
    return even.next;
}

public static ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

public static ListNode mergeList(ListNode l1, ListNode l2){
    // 我用递归
    if (l1 == null) 
        return l2;
    if (l2 == null)
        return l1;
    if (l1.val < l2.val) {
        l1.next = mergeList(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeList(l1, l2.next);
        return l2;
    }
}

17. 分隔链表

https://leetcode-cn.com/problems/partition-list/

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode node1 = dummy1, node2 = dummy2;
        while (head != null){
            if (head.val < x){
                node1.next = head;
                // 你左脚走
                head = head.next;
                // 1也左脚走
                node1 = node1.next;
                // 直接割，我不需要
                node1.next = null;
            } else {
                node2.next = head;
                head = head.next;
                node2 = node2.next;
                node2.next = null;
            }
        }
        node1.next = dummy2.next;
        return dummy1.next;
    }
}

18 排序链表

https://leetcode-cn.com/problems/sort-list/

class Solution {
    public ListNode sortList(ListNode head) {
        return head == null ? null : mergeSort(head);
    }
    private ListNode mergeSort(ListNode head) {
        if (head.next == null)
            return head;
        ListNode p = head, q = head, pre = null;
        while (q != null && q.next != null){
            pre = p;
            p = p.next;
            q = q.next.next;
        }
        pre.next = null;
        ListNode l = mergeSort(head);
        ListNode r = mergeSort(p);
        return merge(l, r);
    }

    private ListNode merge(ListNode l1, ListNode l2){
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
        if (l1.val < l2.val){
            l1.next = merge(l1.next, l2);
            return l1;
        } else {
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }
}

143. 重排链表

https://leetcode-cn.com/problems/reorder-list/

class Solution {
    public void reorderList(ListNode head) {
        LinkedList<ListNode> queue = new LinkedList<>();
        ListNode cur = head;
        while (cur != null) {
            queue.addLast(cur);
            cur = cur.next;
        }
        while (!queue.isEmpty()) {
            if (cur == null)
                cur = queue.pollFirst();
            else {
                cur.next = queue.pollFirst();
                cur = cur.next;
            }
            cur.next = queue.pollLast();
            cur = cur.next;
        }
        if (cur != null) 
            cur.next = null;
    }
}

19. 删除链表的倒数第N个节点

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        while (n-- > 0) {
            fast = fast.next;
        }
        // 这里没懂， 得举例子就懂了
        if (fast == null) return head.next;
        ListNode slow = head;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 这里也懂了...举个例子就行
        slow.next = slow.next.next;
        return head;
    }
}