＜习题集＞＜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;}