Рубрики

Java программа для обратного связанного списка

Учитывая указатель на головной узел связанного списка, задача состоит в том, чтобы полностью изменить связанный список. Нам нужно изменить список, изменив ссылки между узлами.

Примеры:

Input : Head of following linked list  
       1->2->3->4->NULL
Output : Linked list should be changed to,
       4->3->2->1->NULL

Input : Head of following linked list  
       1->2->3->4->5->NULL
Output : Linked list should be changed to,
       5->4->3->2->1->NULL

Input : NULL
Output : NULL

Input  : 1->NULL
Output : 1->NULL

Итерационный метод

Джава

// Java-программа для обращения к связанному списку

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d) {

            data = d;

            next = null;

        }

    }

  

    / * Функция перевернуть связанный список * /

    Node reverse(Node node) {

        Node prev = null;

        Node current = node;

        Node next = null;

        while (current != null) {

            next = current.next;

            current.next = prev;

            prev = current;

            current = next;

        }

        node = prev;

        return node;

    }

  

    // печатает содержимое двойного связанного списка

    void printList(Node node) {

        while (node != null) {

            System.out.print(node.data + " ");

            node = node.next;

        }

    }

  

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        list.head = new Node(85);

        list.head.next = new Node(15);

        list.head.next.next = new Node(4);

        list.head.next.next.next = new Node(20);

          

        System.out.println("Given Linked list");

        list.printList(head);

        head = list.reverse(head);

        System.out.println("");

        System.out.println("Reversed linked list ");

        list.printList(head);

    }

}

  

  
// Этот код предоставлен Mayank Jaiswal

Рекурсивный метод:

void recursiveReverse(struct Node** head_ref)

{

    struct Node* first;

    struct Node* rest;

       

    / * пустой список * /

    if (*head_ref == NULL)

       return;   

  

    / * предположим, что first = {1, 2, 3}, rest = {2, 3} * /

    first = *head_ref;  

    rest  = first->next;

  

    / * Список имеет только один узел * /

    if (rest == NULL)

       return;   

  

    / * инвертировать список остальных и поместить первый элемент в конец * /

    recursiveReverse(&rest);

    first->next->next  = first;  

      

    / * хитрый шаг - см. диаграмму * /

    first->next  = NULL;          

  

    / * исправить указатель головы * /

    *head_ref = rest;              

}

Более простой и рекурсивный метод

Джава

// Java-программа для обращения к связанному списку

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d) {

            data = d;

            next = null;

        }

    }

  

    // Простая и хвостовая рекурсивная функция для обратного

    // связанный список. prev передается как NULL изначально.

    Node reverseUtil(Node curr, Node prev) {

  

        / * Если последний узел пометил его головой * /

        if (curr.next == null) {

            head = curr;

  

            / * Обновление рядом с предыдущим узлом * /

            curr.next = prev;

            return null;

        }

  

        / * Сохранить curr-> следующий узел для рекурсивного вызова * /

        Node next1 = curr.next;

  

        / * и обновлять дальше .. * /

        curr.next = prev;

  

        reverseUtil(next1, curr);

        return head;

    }

  

    // печатает содержимое двойного связанного списка

    void printList(Node node) {

        while (node != null) {

            System.out.print(node.data + " ");

            node = node.next;

        }

    }

  

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        list.head = new Node(1);

        list.head.next = new Node(2);

        list.head.next.next = new Node(3);

        list.head.next.next.next = new Node(4);

        list.head.next.next.next.next = new Node(5);

        list.head.next.next.next.next.next = new Node(6);

        list.head.next.next.next.next.next.next = new Node(7);

        list.head.next.next.next.next.next.next.next = new Node(8);

  

        System.out.println("Original Linked list ");

        list.printList(head);

        Node res = list.reverseUtil(head, null);

        System.out.println("");

        System.out.println("");

        System.out.println("Reversed linked list ");

        list.printList(res);

    }

}
// Этот код предоставлен Mayank Jaiswal

Пожалуйста, обратитесь к полной статье на Обратный связанный список для более подробной информации!

Рекомендуемые посты:

Java программа для обратного связанного списка

0.00 (0%) 0 votes