＜习题集＞＜LeetCode＞＜链表＞＜2/19/21/23/24＞

目录

2. 两数相加

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

21. 合并两个有序链表

23. 合并 K 个升序链表

24. 两两交换链表中的节点

---

---

2. 两数相加

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

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //head是cur链表头节点，cur用于记录相加和的链表；
        ListNode head = new ListNode();
        ListNode cur = head;
        //进位标志；
        int flag = 0;
        //两个用于相加的链表都走到null，结束；
        while(l1!=null || l2!=null){
            int l1Val = l1==null ? 0 : l1.val;
            int l2Val = l2==null ? 0 : l2.val;
            //计算和；
            int sum = l1Val+l2Val+flag;
            //新建节点加入cur链表中；
            cur.next = new ListNode(sum%10);
            //判断是否需要进位；
            if(sum>=10){
                flag=1;
            }else {
                flag=0;
            }
            //判断两个用于相加的链表是否走到null，没到的才继续走；
            if(l1!=null){
                l1 = l1.next;
            }
            if(l2!=null){
                l2 = l2.next;
            }
            //cur链表也向后移动；
            cur = cur.next;
        }
        //走到这里代表两个链表已经遍历完毕；
        //但是可能最后一次相加也产生了进位，因此在这里要判断；
        if(flag == 1){
            cur.next = new ListNode(1);
        }
        //头节点是空值，返回头节点的下一节点；
        return head.next;
    }

---

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

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

    public ListNode removeNthFromEnd(ListNode head, int n) {
        //创建快慢指针，两个指针的next为head；
        ListNode fast = new ListNode();
        ListNode slow = new ListNode();
        fast.next = head;
        slow.next = head;
        //记录慢指针的头节点，用于返回；
        ListNode root = slow;
        //快指针先走n步；
        for (int i=n;i>0;i--){
            fast = fast.next;
            //处理n大于链表长度的情况；
            if(fast == null){
                return null;
            }
        }
        //依次移动快慢指针，直到快指针的next为null；
        //此时代表慢指针到达要删除的元素的前一位值；
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        //删除下一元素；
        slow.next = slow.next.next;
        //返回；
        return root.next;
    }

---

21. 合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/description/

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //创建头节点和一个用于移动的节点cur；
        ListNode head = new ListNode(0);
        ListNode cur = head;
        //边移动，边比较节点的值，并将比较结果赋值，直到有一个链表走完；
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        //判断是哪个链表走完了，把另一个链表在尾部续上；
        if(list1 == null){
            cur.next = list2;
        }
        if(list2 == null){
            cur.next = list1;
        }
        //返回记录的head；
        return head.next;
    }

---

23. 合并 K 个升序链表

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

    public ListNode mergeKLists(ListNode[] lists) {
        //建立链表；
        ListNode root = null;
        //不断将链表元素两两合并；
        for (ListNode list : lists) {
            root = mergeTwoLists(root, list);
        }
        //返回链表；
        return root;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //创建头节点和一个用于移动的节点cur；
        ListNode head = new ListNode(0);
        ListNode cur = head;
        //边移动，边比较节点的值，并将比较结果赋值，直到有一个链表走完；
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        //判断是哪个链表走完了，把另一个链表在尾部续上；
        if(list1 == null){
            cur.next = list2;
        }
        if(list2 == null){
            cur.next = list1;
        }
        //返回记录的head；
        return head.next;
    }

---

24. 两两交换链表中的节点

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

    public ListNode swapPairs(ListNode head) {
        //基本思路就是站在前一个节点(后续简称0节点)，向后望两个节点。
        //并对这两个节点做顺序调换，之后0节点向后移动；

        //创建移动的节点指针，这个节点指向head，这个就是一开始的0节点；
        ListNode cur = new ListNode();
        cur.next = head;
        //记录头节点地址，用于返回；
        ListNode root = cur;

        while(true){
            //没有后续节点的情况；
            if(cur.next == null){
                break;
            }
            //仍存在两个后续节点的情况；
            if(cur.next.next != null){
                //记录下一次需要调整顺序的节点；
                ListNode temp2 = cur.next.next.next;
                //调整顺序；
                ListNode temp1 = cur.next;
                cur.next = cur.next.next;
                cur = cur.next;
                cur.next = temp1;
                //将节点移动到下一次调整的0节点处；
                cur = cur.next;
                cur.next = temp2;
            }else{
                //只剩一个节点的情况；
                break;
            }
        }
        //代码运行到这代表，0节点之后已经没有节点或只剩一个节点；
        //返回记录的头节点；
        return root.next;
    }