合并两个链表【LC1669】
You are given two linked lists: list1 and list2 of sizes n and m respectively.
Remove list1’s nodes from the ath node to the bth node, and put list2 in their place.
The blue edges and nodes in the following figure indicate the result:
Build the result list and return its head.
- 思路：遍历链表找到list1中的第a−1个节点和第b+1个节点，然后将第a−1个节点指向list2链表的初始节点，list2链表的尾节点指向list1中的第b+1个节点
- 实现
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) { ListNode dummyNode = new ListNode(-1, list1); ListNode pre = dummyNode; ListNode cur = dummyNode.next; int idx = 0; while (idx != a){ pre = cur; cur = cur.next; idx++; } while (idx != b){ cur = cur.next; idx++; } pre.next = list2; while (list2.next != null){ list2 = list2.next; } list2.next = cur.next; cur.next = null; return list1; } }
。复杂度分析
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
