연결된 목록 반전

연결된 목록 반전은 데이터 구조 및 알고리즘에서 흥미로운 문제입니다. 이 튜토리얼에서는 Linked List를 뒤집은 다음 Java를 사용하여 구현하는 다양한 알고리즘에 대해 논의할 것입니다.

연결된 목록 반전

LinkedList는 데이터를 선형 방식으로 저장하는 데이터 구조입니다. 연속적이지는 않지만. LinkedList의 모든 요소에는 데이터 부분과 LinkedList의 다음 요소에 대한 주소가 포함됩니다. LinkedList 요소는 일반적으로 노드로 알려져 있습니다.

Double LinkedList는 두 개의 주소를 저장합니다. 이전 요소와 다음 요소의 주소입니다.

• 반복적 접근 방식
• 재귀 접근법

연결된 목록을 되돌리기 위한 반복적 접근 방식

다음은 LinkedList를 되돌리기 위해 따라야 할 단계입니다. 3개의 인스턴스 생성: 현재, 다음, 이전. 전류가 null이 아닐 때까지 다음을 반복합니다.

• 다음 포인터에 현재 요소의 다음 노드를 저장합니다.
• 현재 노드의 다음 노드를 이전 노드로 설정합니다. 이것은 MVP 라인입니다.
• 이전에서 현재로 이동합니다.
• 현재 요소를 다음 요소로 이동합니다.

결국 전류는 마지막 요소보다 한 단계 앞서 갔기 때문에 도달한 마지막 요소에 헤드를 설정해야 합니다. 이것은 이전 버전에서 사용할 수 있습니다. 머리를 이전으로 설정하십시오. 따라서 이전 LinkedList의 마지막 요소인 LinkedList의 새 헤드가 있습니다.

다음은 LinkedList의 매우 간단한 구현입니다. 이것은 생산 준비가 된 구현이 아니며 연결 목록을 되돌리는 알고리즘에 집중할 수 있도록 단순하게 유지했습니다.

package com.journaldev.linkedlist.reverse;

public class MyLinkedList {

	public Node head;

	public static class Node {

		Node next;

		Object data;

		Node(Object data) {
			this.data = data;
			next = null;
		}
	}
}

연결된 목록을 반복적으로 반전하고 해당 요소를 인쇄하는 Java 프로그램은 다음과 같습니다.

package com.journaldev.linkedlist.reverse;

import com.journaldev.linkedlist.reverse.MyLinkedList.Node;

public class ReverseLinkedList {

	public static void main(String[] args) {
		MyLinkedList myLinkedList = new MyLinkedList();
		myLinkedList.head = new Node(1);
		myLinkedList.head.next = new Node(2);
		myLinkedList.head.next.next = new Node(3);

		printLinkedList(myLinkedList);
		reverseLinkedList(myLinkedList);
		printLinkedList(myLinkedList);

	}

	public static void printLinkedList(MyLinkedList linkedList) {
		Node h = linkedList.head;
		while (linkedList.head != null) {
			System.out.print(linkedList.head.data + " ");
			linkedList.head = linkedList.head.next;
		}
		System.out.println();
		linkedList.head = h;
	}

	public static void reverseLinkedList(MyLinkedList linkedList) {
		Node previous = null;
		Node current = linkedList.head;
		Node next;
		while (current != null) {
			next = current.next;
			current.next = previous;
			previous = current;
			current = next;
		}
		linkedList.head = previous;
	}

}

산출:

1 2 3 
3 2 1 

연결된 목록을 재귀적으로 되돌리기

LinkedList를 재귀적으로 되돌리려면 LinkedList를 헤드와 나머지 두 부분으로 나눌 필요가 있습니다. 머리는 처음에 첫 번째 요소를 가리킵니다. 나머지는 머리에서 다음 요소를 가리킵니다.

두 번째 마지막 요소까지 LinkedList를 재귀적으로 순회합니다. 마지막 요소 세트에 도달하면 이를 머리로 설정합니다. 여기에서 LinkedList의 시작 부분에 도달할 때까지 다음을 수행합니다. node.next.next = node; node.next = null; 원본 헤드의 트랙을 잃지 않기 위해 헤드 인스턴스의 복사본을 저장합니다.

public static Node recursiveReverse(Node head) {
	Node first;

	if (head==null || head.next == null)
		return head;

	first = recursiveReverse(head.next);
	head.next.next = head;
	head.next = null;

	return first;
}

LinkedList의 끝으로 이동하기 위해 재귀 호출에서 head.next를 전달합니다. 끝에 도달하면 두 번째 마지막 요소를 마지막 요소의 다음으로 설정하고 두 번째 마지막 요소의 다음 포인터를 NULL로 설정합니다. 마지막 요소는 새 헤드로 표시됩니다. 다음 코드를 사용하여 재귀 접근 방식을 사용하여 연결된 목록을 뒤집습니다.

myLinkedList.head = recursiveReverse(myLinkedList.head);

출력은 이전 반복 접근 방식으로 유지됩니다.

연결된 목록 반전의 시공간 복잡도

시간 복잡도 - O(n) 공간 복잡도 - O(1)

GitHub 리포지토리에서 전체 코드와 더 많은 DS 및 알고리즘 예제를 확인할 수 있습니다.