음.. 좀 고민을 했다. 한개씩 노드를 돌면서 순회는 해야겠는데 어떻게하면 간단해질까 싶었는데..
우선, 문제를 작게 분할해서 보면 인접한 두 노드의 관계가 변하는것이다. 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;
}
}
}
|
