# 더블 링크드 리스트 뒤집기 알고리즘 (C# 버전)

음.. 좀 고민을 했다. 한개씩 노드를 돌면서 순회는 해야겠는데 어떻게하면 간단해질까 싶었는데.. 우선, 문제를 작게 분할해서 보면 인접한 두 노드의 관계가 변하는것이다. 1개의 노드를 기준으로 보면 next 값과 prev 값이 변하는 것. 예를들면, Node#1           Node#2 -value : 1          -value : 2 -prev : null        -prev : Node#1 -next : Node#2    -next : null 여기서, 각 노드의 prev와 next값을 교환해주면, 거꾸로 뒤집은 모양새가 나온다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace test00 { /* * 더블 링크드 리스트의 순서를 뒤바꾸기 알고리즘 */ class Node { public int value; public Node prev; public Node next; } class Program { static void Main(string[] args) { Node head = CreateTestNodes(5); Print(head); Node reversed = Reverse(head); Print(reversed); } #region Stub static Node CreateTestNodes(int count) { var nodes = new Node[count]; for (int i = 0; i < count; i++) nodes[i] = new Node() { value = i + 1 }; for (int i = 1; i < count; i++) nodes[i].prev = nodes[i - 1]; for (int i = 0; i < count - 1; i++) nodes[i].next = nodes[i + 1]; return nodes[0]; } static void Print(Node head) { var node = head; while (node != null) { Console.Write(node.value + " "); node = node.next; } Console.WriteLine(); } #endregion static Node Reverse(Node head) { Node traverse = head; while (traverse != null) { if (traverse.next == null) head = traverse; Node tmp = traverse.next; // prev, next를 swap. traverse.next = traverse.prev; traverse.prev = tmp; traverse = traverse.prev; } return head; } } }