Chương trình Java lấy phần tử giữa của LinkedList trong một lần duyệt

Trong bài viết này, chúng ta sẽ hiểu cách lấy phần tử giữa của LinkedList trong một lần duyệt (single iteration). Lớp java.util.LinkedList thực hiện các thao tác như mong đợi cho danh sách liên kết kép. Các thao tác truy xuất theo chỉ số sẽ duyệt list từ đầu hoặc cuối, tùy phía gần chỉ số chỉ định hơn.

Minh họa dưới đây:

Giả sử đầu vào là:

Input linked list: 100 200 330

Đầu ra mong muốn:

The middle element of the list is: 200

Thuật toán

Bước 1 - BẮT ĐẦU 
Bước 2 - Khai báo LinkedList input_list, 5 node: head, first_node, second_node, pointer_1, pointer_2 
Bước 3 - Định nghĩa giá trị 
Bước 4 - Dùng while loop duyệt linked list, lấy phần tử giữa bằng cách duyệt với pointer_1 và pointer_2 cho đến khi pointer_1.next không null 
Bước 5 - Hiển thị giá trị pointer_2 làm kết quả 
Bước 6 - DỪNG

Ví dụ 1

Gom thao tác dưới 'main'.

public class LinkedList { 
    Node head; 
    static class Node { 
        int value; 
        Node next; 
        Node(int d) { 
            value = d; 
            next = null; 
        } 
    } 
    
    public static void main(String[] args) { 
        LinkedList input_list = new LinkedList(); 
        input_list.head = new Node(100); 
        Node second_node = new Node(200); 
        Node third_node = new Node(330); 
        input_list.head.next = second_node; 
        second_node.next = third_node; 
        Node current_node = input_list.head; 
        System.out.print("The linked list is defined as: " ); 
        while (current_node != null) { 
            System.out.print(current_node.value + " "); 
            current_node = current_node.next; 
        } 
        Node pointer_1 = input_list.head; 
        Node pointer_2 = input_list.head; 
        while (pointer_1.next != null) { 
            pointer_1 = pointer_1.next; 
            if(pointer_1.next != null) { 
                pointer_1 = pointer_1.next; 
                pointer_2 = pointer_2.next; 
            } 
        } 
        System.out.println("\nThe middle element of the list is: " + pointer_2.value); 
    } 
}

Kết quả

The linked list is defined as: 100 200 330 
The middle element of the list is: 200

Ví dụ 2

Đóng gói thao tác vào hàm thể hiện lập trình hướng đối tượng.

public class LinkedList { 
    Node head; 
    static class Node { 
        int value; 
        Node next; 
        Node(int d) { 
            value = d; 
            next = null; 
        } 
    } 
    
    static void get_middle_item(LinkedList input_list){ 
        Node pointer_1 = input_list.head; 
        Node pointer_2 = input_list.head; 
        while (pointer_1.next != null) { 
            pointer_1 = pointer_1.next; 
            if(pointer_1.next != null) { 
                pointer_1 = pointer_1.next; 
                pointer_2 = pointer_2.next; 
            } 
        } 
        System.out.println("\nThe middle element of the list is: " + pointer_2.value); 
    } 
    
    public static void main(String[] args) { 
        LinkedList input_list = new LinkedList(); 
        input_list.head = new Node(100); 
        Node second_node = new Node(200); 
        Node third_node = new Node(330); 
        input_list.head.next = second_node; 
        second_node.next = third_node; 
        Node current_node = input_list.head; 
        System.out.print("The linked list is defined as: " ); 
        while (current_node != null) { 
            System.out.print(current_node.value + " "); 
            current_node = current_node.next; 
        } 
        get_middle_item(input_list); 
    } 
}

Kết quả

The linked list is defined as: 100 200 330 
The middle element of the list is: 200