연결된 목록 뒤집기

연결 리스트를 뒤집는 것은 데이터 구조와 알고리즘에서 흥미로운 문제입니다. 이 튜토리얼에서는 연결 리스트를 뒤집는 다양한 알고리즘에 대해 이야기하고, 그것을 자바로 구현해 보겠습니다.

연결 리스트 뒤집기

LinkedList는 데이터를 선형 방식으로 저장하는 데이터 구조입니다. 연속적으로 저장되지는 않습니다. LinkedList의 각 요소는 데이터 부분과 LinkedList의 다음 요소로의 주소를 포함합니다. LinkedList의 요소들은 일반적으로 노드라고 불립니다.

이중 연결 리스트는 이전 요소와 다음 요소의 두 가지 주소를 저장합니다.

LinkedList를 자리에서 뒤집으려면 다음 요소가 이제 이전 요소를 가리키도록 포인터를 뒤집어야 합니다. 다음은 입력 및 출력입니다. LinkedList의 헤드는 첫 번째 노드입니다. 다른 요소는 이를 위한 주소를 저장하지 않습니다. LinkedList의 꼬리는 마지막 노드입니다. 이 노드에 저장된 다음 주소는 null입니다. 다음을 사용하여 LinkedList를 뒤집을 수 있습니다:

• 반복적인 접근
• 재귀적인 접근

LinkedList를 뒤집기 위한 반복적인 접근

LinkedList를 반복적으로 뒤집으려면 다음과 이전 요소의 참조를 저장해야합니다. LinkedList의 메모리 주소 포인터를 다음 요소로 교환할 때 참조가 손실되지 않도록합니다. 다음 설명은 참조를 변경하여 LinkedList를 뒤집는 방법을 보여줍니다.

LinkedList를 뒤집는 단계는 다음과 같습니다. current, next, previous 3 개의 인스턴스를 생성합니다. current가 null이 아닐 때까지 다음을 반복합니다.

• current 요소의 다음 노드를 next 포인터에 저장합니다.
• current 노드의 다음을 previous로 설정합니다. 이것은 MVP 라인입니다.
• previous를 current로 이동합니다.
• current 요소를 next로 이동합니다.

마지막으로, current가 마지막 요소보다 한 자리 앞으로 이동했으므로 head를 도달한 마지막 요소로 설정해야합니다. 이는 previous에 사용할 수 있습니다. head를 previous로 설정합니다. 따라서 LinkedList의 새로운 head는 이전 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;
		}
	}
}

LinkedList를 반복적으로 뒤집고 요소를 출력하는 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 

링크드 리스트를 재귀적으로 뒤집기

링크드 리스트를 재귀적으로 뒤집으려면 링크드 리스트를 머리와 나머지 두 부분으로 나눠야 합니다. 머리는 처음에 첫 번째 요소를 가리킵니다. 나머지는 머리에서 다음 요소를 가리킵니다.

우리는 링크드 리스트를 재귀적으로 탐색하여 두 번째 마지막 요소에 도달할 때까지 진행합니다. 마지막 요소에 도달하면 해당 요소를 머리로 설정합니다. 그런 다음 링크드 리스트의 시작 지점에 도달할 때까지 다음을 수행합니다. node.next.next = node; node.next = null; 원본 머리를 잃지 않기 위해 머리 인스턴스의 사본을 저장합니다.

위 과정의 설명은 다음과 같습니다. 링크드 리스트를 재귀적으로 뒤집는 Java 프로그램은 다음과 같습니다:

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;
}

재귀 호출에서 단순히 head.next를 전달하여 링크드 리스트의 끝으로 이동합니다. 끝에 도달하면 두 번째 마지막 요소를 마지막 요소의 다음 요소로 설정하고 두 번째 마지막 요소의 다음 포인터를 NULL로 설정합니다. 마지막 요소가 새 머리로 표시됩니다. 재귀적 접근을 사용하여 링크드 리스트를 뒤집으려면 다음 코드를 사용하십시오.

myLinkedList.head = recursiveReverse(myLinkedList.head);

출력은 이전 반복적인 방법과 동일합니다.

연결 리스트를 뒤집는 데 필요한 공간 시간 복잡도

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

완전한 코드 및 더 많은 DS 및 알고리즘 예제를 확인할 수 있습니다. GitHub 저장소에서.