Hợp nhất danh sách liên kết vào danh sách khác tại vị trí xen kẽ trong Java

Cho hai danh sách liên kết List_1 và List_2. Nhiệm vụ: hợp nhất các phần tử của List_2 vào List_1 tại các vị trí xen kẽ (alternate positions). Nếu List_2 còn dư phần tử thì in ra phần tử còn lại của List_2.

Ví dụ

Đầu vào:

List_1: 10 → 2 → 1 → 4 → 2 → 5 → 5
List_2: 3 → 1 → 7 → 2

Đầu ra: Danh sách đã hợp nhất: 10 → 3 → 2 → 1 → 1 → 4 → 2 → 5 → 5

List_2 còn lại: 7 → 2

Đầu vào:

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

Đầu ra: Merged List: 11 → 14 → 12 → 15 → 13

List_2 còn lại: 16 → 17 → 18

Phương pháp tiếp cận

• Tạo head node trỏ đến node đầu tiên
• Lớp Node có value, next, constructor Node(int val)
• Phương thức add(int val): Tạo node mới, new_node.next = head, head = new_node
• Phương thức mergeList(TutorialPoint list):
  • n1_curr = head, n2_curr = list.head
  • 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 (cập nhật head List_2 thành phần tử còn lại)
• Trong main(): Tạo list_1, list_2, thêm phần tử, gọi mergeList, in kết quả

Ví dụ mã Java

public class TutorialPoint {
    Node head;
    
    class Node {
        int value;
        Node next;
        Node(int val) {
            value = val;
            next = null;
        }
    }
    
    void add(int updated_value) {
        Node new_node = new Node(updated_value);
        new_node.next = head;
        head = new_node;
    }
    
    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();
    }
}

Đầu ra

Merged list is: 11 14 12 15 13 16