链表

BM1 反转链表

public class Solution {
    // 迭代法：
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode pre = null, next = head.next;
        while(next != null){
            head.next = pre;
            pre = head;
            head = next;
            next = head.next;
        }
        head.next = pre;
        return head;
    }
    
    // 递归法：
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode last = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

BM2 链表内指定区间反转

public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(m == 1) return reverseN(head, n);// 反转前n个节点
        // 递归操作
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }
    
    // 反转前n个节点
    ListNode successor = null;
    public ListNode reverseN(ListNode head, int n){
        if(n == 1){// 记录successor，一个节点无需反转，直接返回
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return last;
    }
}

BM3 k个一组反转链表

public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        if(head == null || head.next == null) return head;
        // dumpy虚拟节点，指向头部
        ListNode dumpy = new ListNode(-1);
        dumpy.next = head;
        // end保存每一组k个节点的最后一个节点
        ListNode end = dumpy;
        // 判断该组元素是否够k个，不够则直接退出循环
        for(int i = 0; i < k; i++){
            if(end.next == null) return head;
            end = end.next;
        }
        // 反转前n个节点
        dumpy.next = reverseN(head, k);
        // 对于完成反转节点的组后面的节点，继续k个一组进行反转
        head.next = reverseKGroup(head.next, k);
        return dumpy.next;
    }
    
    // 反转k个节点
    ListNode successor = null;
    public ListNode reverseN(ListNode head, int k){
        if(k == 1){
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, k - 1);
        head.next.next = head;
        head.next = successor;
        return last;
    }
}

BM4 合并两个排序链表

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        // 创建一个虚拟节点，用于返回
        ListNode dumpy = new ListNode(-1);
        ListNode cur1 = list1, cur2 = list2;
        ListNode cur =dumpy;
        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                cur.next = cur1;
                cur1 = cur1.next;
            } else{
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        // 其中一个为null
        cur.next = cur1 == null ? cur2 : cur1;
        return dumpy.next;
    }
}

BM5 合并k个有序链表

import java.util.ArrayList;
import java.util.PriorityQueue;
public class Solution {
    // 采用最小堆处理
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        // 创建虚拟头结点dumpy（方便返回结果）和cur节点（标记当前节点）
        ListNode dumpy = new ListNode(-1), cur = dumpy;
        // 特殊情况处理
        if(lists.size() == 0) return dumpy.next;
        // 创建一个最小堆优先序列
        PriorityQueue<ListNode> pQueue = new PriorityQueue<ListNode>(lists.size(), (a, b) -> (a.val - b.val));
        // 将每个链表的头结点添加至最小堆中
        for(ListNode head : lists){
            if(head != null) pQueue.add(head);
        }
        // 依次从最小堆中取出堆顶元素，添加至结果链表
        while(!pQueue.isEmpty()){
            ListNode node = pQueue.poll();
            cur.next = node;
            cur = cur.next;
            if(node.next != null) pQueue.add(node.next);
        }
        return dumpy.next;
    }
}

BM6 判断链表是否有环

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 快慢指针
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) return true;
        }
        return false;
    }
}

BM7 链表中环的入口结点

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 采用快慢指针
        ListNode fast = pHead, slow = pHead;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                slow = pHead;
                while(slow != fast){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        // 没有坏，返回空节点
        return null;
    }
}

BM8 链表中倒数最后k个节点

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // 双指针
        ListNode left = pHead, right = pHead;
        for(int i = 0; i < k; i++){
            if(right == null) return null;
            right = right.next;
        }
        while(right != null){
            left = left.next;
            right = right.next;
        }
        return left;
    }
}

BM9 删除链表中的倒数第k个节点

public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // 双指针，先找到待删除节点的前一个节点
        // 虚拟节点dumpy指向头结点的前一个节点，方便返回头节点
        ListNode dumpy = new ListNode(-1);
        dumpy.next = head;
	// left指向dumpy，可以得到待删除节点的前一个节点
        ListNode left = dumpy, right = head;
        for(int i = 0; i < n; i++){
            right = right.next;
        }
        while(right != null){
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return dumpy.next;
    }
}

BM10 两个链表的第一个公共节点

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // 双指针
        // 先判断是否有环
        if(!isCommonNode(pHead1, pHead2)) return null;
        // 有环，则找到第一个公共节点
        ListNode cur1 = pHead1, cur2 = pHead2;
        while(cur1 != cur2){
            cur1 = cur1 == null ? pHead2 : cur1.next;
            cur2 = cur2 == null ? pHead1 : cur2.next;
        }
        return cur1;
    }
    // 判断是否存在环
    public boolean isCommonNode(ListNode pHead1, ListNode pHead2){
        if(pHead1 == null || pHead2 == null) return false;
        // 判断是否有公共节点：通过判断两个链表的最后一个节点是否相同
        while(pHead1.next != null) pHead1 = pHead1.next;
        while(pHead2.next != null) pHead2 = pHead2.next;
        return pHead1.val == pHead2.val;
    }
}

BM11 链表相加（二）

public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        // 先反转两个链表，然后遍历相加,最后将结果链表反转
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        // 反转两个链表
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        // 虚拟节点dumpy用于返回答案，cur用于指向当前节点
        ListNode dumpy = new ListNode(-1), cur = dumpy;
        // carry纪录进位
        int carry = 0;
        while(head1 != null && head2 != null){
            // 对应位求和
            int sum = head1.val + head2.val + carry;
            carry = sum / 10;
            ListNode node = new ListNode(sum % 10);
            cur.next = node;
            cur = cur.next;
            head1 = head1.next;
            head2 = head2.next;
        }
        // 至少有一个链表为null
        if(head1 == null && head2 == null) {
            if(carry != 0) cur.next = new ListNode(carry);
        }else if(head1 == null){
            ListNode cur2 = head2;
            while(carry != 0 && cur2.next != null) {
                cur2.val += carry;
                carry = cur2.val / 10;
                cur2.val %= 10;
                cur2 = cur2.next;
            }
            if(carry != 0) {// 上面循环结束条件为cur2.next != null
                carry = carry + cur2.val;
                cur2.val = carry >= 10 ? carry % 10 : carry;
                carry /= 10;
            }
            if(carry != 0) cur2.next = new ListNode(carry);
            cur.next = head2;
         }else {
            ListNode cur1 = head1;
            while(carry != 0 && cur1.next != null) {
                cur1.val += carry;
                carry = cur1.val / 10;
                cur1.val %= 10;
                cur1 = cur1.next;
            }
            if(carry != 0) {// 上面循环结束条件为cur2.next != null
                carry = carry + cur1.val;
                cur1.val = carry >= 10 ? carry % 10 : carry;
                carry /= 10;
            }
            if(carry != 0) cur1.next = new ListNode(carry);
            cur.next = head1;
        }
        dumpy = reverseList(dumpy.next);
        return dumpy;
    }
    
    // 反转两个链表
    public ListNode reverseList(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

BM12 单链表的排序

public class Solution {
    public ListNode sortInList (ListNode head) {
        boolean flag = true;// 标记本次是否有交换
        ListNode cur = head;
        while(flag){
            flag = false;
            while(cur.next != null){
                if(cur.val > cur.next.val){// 无序，则排序
                    swap(cur, cur.next);
                    flag = true;
                }
                cur = cur.next;
            }
            // 遍历到最后一个节点
            cur = head;
        }
        return head;
    }
    // 交换两个节点的值
    public void swap(ListNode node1, ListNode node2){
        int temp = node1.val;
        node1.val = node2.val;
        node2.val = temp;
    }
}

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

public class Solution {
    public boolean isPail (ListNode head) {
        if(head == null || head.next == null) return true;
        // 快慢指针找到中间位置，反转后半部分，遍历
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        // 若只有两个节点，则比较两个元素值是否相等
        if(slow.next == null) return slow.val == head.val;
        // 否则，元素节点超过两个
        slow.next = reverseList(slow.next);
        fast = slow.next;
        slow = head;
        while(fast != null){
            if(fast.val != slow.val) return false;
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
    
    // 反转链表，采用迭代方法
    public ListNode reverseList(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode pre = null, next = head.next;
        while(next != null){
            head.next = pre;
            pre = head;
            head = next;
            next = head.next;
        }
        head.next = pre;
        return head;
    }
}

BM14 链表的奇偶重排

public class Solution {
    public ListNode oddEvenList (ListNode head) {
        if(head == null || head.next == null) return head;
        // 将偶数位节点取出构成一个链表，奇数位构成一个链表，然后将两个链表接起来
        ListNode dumpy1 = new ListNode(-1);// 奇数位链表
        ListNode dumpy2 = new ListNode(-1);// 偶数位链表
        dumpy1.next = head;
        dumpy2.next = head.next;
        ListNode cur1 = head, cur2 = head.next;
        // 拆分成两个链表
        while(cur1.next != null && cur2.next != null){
            cur1.next = cur1.next.next;
            cur1 = cur1.next;
            cur2.next = cur2.next.next;
            cur2 = cur2.next;
        }
        // 拼接两个链表
        cur1.next = dumpy2.next;
        return dumpy1.next;
    }
}

BM15 删除有序链表中重复的元素I

public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode cur = head, next = head.next;
        // cur前面的节点均为不重复的（包括cur）
        while(next != null){
            // 若cur与next相等，则删除next
            if(cur.val == next.val) cur.next = next.next; 
            else cur = cur.next;// 否则，不相等，cur后移
            //next后移
            next = next.next;
        }
        return head;
    }
}

BM16 删除有序链表中重复的元素II

public class Solution {
     public ListNode deleteDuplicates (ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dumpy = new ListNode(-1);
        dumpy.next = head;
        int num = 0;// 记录cur前面最有后一个重复的数字
        ListNode prev = dumpy, cur = head, next = head.next;
        while(next != null){
            if(cur.val == next.val){// 相等
                num = cur.val;
            } else{ // 不相等
                if(num != cur.val) prev = prev.next;
                prev.next = next;
                cur = next;
            }
            next = next.next;
        }
	// 若cur没有重复过，则添加到结果
        if(num != cur.val) {
             prev.next = cur;
             prev = prev.next;
         }
         prev.next = null;
        return dumpy.next;
    }
}