LeetCode-1669题：合并两个链表（原创）

【题目描述】

        给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。下图中蓝色边和节点展示了操作后的结果：

请你返回结果链表的头指针。

【提示】

1）3 <= list1.length <= 104
2）1 <= a <= b < list1.length - 1
3）1 <= list2.length <= 104

【题目链接】. - 力扣（LeetCode）

【解题代码】

package list;import list.base.ListNode;public class MergeInBetween {public static void main(String[] args) {int[] l1 = new int[]{0, 1, 2, 3, 4, 5, 6};int[] l2 = new int[]{1000000, 1000001, 1000002, 1000003, 1000004};ListNode list1 = ListNode.makeList(l1);ListNode list2 = ListNode.makeList(l2);ListNode list3 = new MergeInBetween().mergeInBetween(list1, 2, 5, list2);list3.printList();}private ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {// 先从list1的首节点走a-1步找到节点a前一节点ListNode preANode = followingNode(list1, a - 1);// 再从a节点走b-a+2步找到节点b+1ListNode nextBNode = followingNode(preANode, b - a + 2);// 找到list2的尾节点ListNode tailNode2 = getTailNode(list2);// 将节点a下一节点指向list2首节点preANode.next = list2;// 将list2的尾节点指向节点b下一个节点tailNode2.next = nextBNode;return list1;}private ListNode followingNode(ListNode node, int step) {int i = 0;ListNode node2 = node;while (i < step) {node2 = node2.next;i++;}return node2;}private ListNode getTailNode(ListNode node) {while (node.next != null) {node = node.next;}return node;}
}

【解题思路】

     根据题目描述，可以得出链表操作完之后：

1. a节点的前一节点指向list2的首节点
2. list2的尾节点指向b的下一节点 

根据上述思路，很快完成代码编写，并提交LeetCode成功

        

【解题步骤】

1.  定义一个函数followingNode，从链表某一节点，向后走step步

   private ListNode followingNode(ListNode node, int step) {int i = 0;ListNode node2 = node;while (i < step) {node2 = node2.next;i++;}return node2;
   }

2. 定义一个函数getTailNode，找到链表尾节点 

   private ListNode getTailNode(ListNode node) {while (node.next != null) {node = node.next;}return node;
   }

3. 先从list1的首节点走a-1步找到节点a前一节点

    ListNode preANode = followingNode(list1, a - 1);

4. 再从a节点走b-a+2步找到节点b+1

   ListNode nextBNode = followingNode(preANode, b - a + 2);

5. 找到list2的尾节点

   ListNode tailNode2 = getTailNode(list2);

6. 将节点a下一节点指向list2首节点

   preANode.next = list2

7. 将list2的尾节点指向节点b下一个节点

   tailNode2.next = nextBNode

8. 最后返回链表list1首节点即可

   return list1;

【思考总结】

1. 链表操作要注意首节点保存和尾节点的获取与保存
2. 所有链表操作基本上都是对三个变量的操作：当前节点curNode，上一节点preNode，下一节点nextNode；
3. 链表遍历时对不停地更新上面三个变量
4. LeetCode解题之前，一定不要看题解，看了就“破功”了！