รวมลิงก์ลิสต์เข้าไปในอีกลิงก์ลิสต์หนึ่งที่ตำแหน่งสลับกันใน Java

ภาพรวมปัญหา

ได้รับลิงก์ลิสต์ 2 ตัว (List_1, List_2) ต้องรวมโหนดของ List_2 เข้า List_1 แบบสลับกัน (alternate positions) หาก List_2 ยาวกว่า โหนดที่เหลือจะอยู่ใน List_2

ตัวอย่าง

ตัวอย่างที่ 1

List_1: 11 → 12 → 13
List_2: 14 → 15 → 16 → 17 → 18

Merged List_1: 11 → 14 → 12 → 15 → 13 → 16
List_2 ที่เหลือ: 17 → 18

ตัวอย่างที่ 2 (รูปภาพ)

List_1: 10 → 2 → 1 → 4 → 5
List_2: 3 → 1 → 2 → 5 → 7 → 2
Merged List_1: 10 → 3 → 2 → 1 → 1 → 4 → 2 → 5 → 5
List_2 ที่เหลือ: 7 → 2

แนวทางการแก้ปัญหา

• ใช้ pointer n1_curr (List_1) และ n2_curr (List_2)
• วนลูป while (n1_curr != null && n2_curr != null):
  • เก็บ n1_next = n1_curr.next, n2_next = n2_curr.next
  • n2_curr.next = n1_next
  • n1_curr.next = n2_curr
  • n1_curr = n1_next, n2_curr = n2_next
• อัปเดต list_2.head = n2_curr (โหนดที่เหลือ)

ตัวอย่างโค้ด Java

public class TutorialPoint {
    Node head;
    class Node { int value; Node next; Node(int val) { value = val; next = null; } }

    void add(int val) { Node n = new Node(val); n.next = head; head = n; }

    void mergeList(TutorialPoint list) {
        Node n1_curr = head, n2_curr = list.head;
        Node n1_next, n2_next;
        while (n1_curr != null && n2_curr != null) {
            n1_next = n1_curr.next;
            n2_next = n2_curr.next;
            n2_curr.next = n1_next;
            n1_curr.next = n2_curr;
            n1_curr = n1_next;
            n2_curr = n2_next;
        }
        list.head = n2_curr;
    }

    public static void main(String args[]) {
        TutorialPoint list_1 = new TutorialPoint();
        TutorialPoint list_2 = new TutorialPoint();
        list_1.add(13); list_1.add(12); list_1.add(11);
        list_2.add(18); list_2.add(17); list_2.add(16); list_2.add(15); list_2.add(14);
        list_1.mergeList(list_2);
        System.out.println("Merged list is:");
        Node temp = list_1.head;
        while (temp != null) { System.out.print(temp.value + " "); temp = temp.next; }
        System.out.println();
    }
}

ผลลัพธ์

Merged list is: 11 14 12 15 13 16