단일 체인 목록 반전

Question

올바른 용어를 사용하길 바랍니다. 단일 체인 목록을 만들었습니다.

class MyStack 
{ 
    public Node Initial { get; set; } 

    public MyStack() 
    { 
     Initial = null; 
    } 

    public void Push(int data) 
    { 
     var node = new Node { Data = data, Next = Initial }; 
     Initial = node; 
    } 

    public int Pop() 
    { 
     int res = Initial.Data; 
     Initial = Initial.Next; 
     return res; 
    } 

    public int Sum() 
    { 
     int sum = 0; 
     Node currentNode = Initial; 
     while (currentNode != null) 
     { 
      sum += currentNode.Data; 
      currentNode = currentNode.Next; 
     } 
     return sum; 
    } 
    public int Count() 
    { 
     int count = 0; 
     Node currentNode = Initial; 
     while (currentNode != null) 
     { 
      count++; 
      currentNode = currentNode.Next; 
     } 
     return count; 
    } 

    public void PrintAll() 
    {  
     Node currentNode = Initial; 
     while(currentNode != null) 
     { 
      Console.WriteLine("tmp.Data = " + currentNode.Data); 
      currentNode = currentNode.Next; 
     } 
    } 
} 
public class Node 
{ 
    public int Data; 
    public Node Next; 
} 

이 같은 것을 할 수있는 의미 :

var s = new MyStack(); 
    s.Push(5); 
    s.Push(3); 
    s.Push(7); 
    s.PrintAll(); 
    Console.WriteLine("Sum: " + s.Sum()); 
    Console.WriteLine("Count: " + s.Count()); 

는 지금, 나는 시도하고 역방향 방법을 만들고 싶어. 이것은 작동하는 것 같습니다 :

public void Reverse() 
{ 
    Node predesesor, location; 
    location = Initial; 
    predesesor = null; 
    while(Initial != null) 
    { 
     Initial = Initial.Next; 
     location.Next = predesesor; 
     predesesor = location; 
     location = Initial; 
    } 
    Initial = predesesor; 
} 

나는 그것이 어떻게 작동하는지 알 수없고 유지하기가 어려울 것입니다. 다른 것보다 더 해킹 된 것처럼 보입니다.

도움이 될 수 있습니까?

가 already있다

public class Node 
{ 
    public int Data; 
    public Node Next; 
    public Node Previous; 
} 

는 당신이 프레임 워크의 이중 연결리스트를 원하는 경우 :

Answer 1

나에게 해킹처럼 보이지 않으며 유지할 항목이 보이지 않습니다 (올바른지 아닌지, 그 외에 무엇을 할 것인가?). 그것이 어떻게 작동하는지 알아 내고 싶다면 종이의 각 단계를 "실행"하십시오. 목록을 그립니다 (예 : 1 -> 3 -> 5 -> 7 -> 9 -> NULL). 언제든지 모든 노드가 가리키는 곳을 표시하고 "단일 단계"를 시작하십시오.

단일 링크 된 목록을 뒤집는 더 깨끗한 방법을 생각할 수 없었습니다. 현재 노드와 이전 노드 사이의 링크를 되돌릴 수 있으려면 다음 노드 (루프 시작 부분의 초기)에 대한 참조가 필요합니다. 그렇지 않으면 원래 목록에서 계속 이동할 수 없습니다.

당신이 할 수있는 일은 변수의 철자를 수정하고 루프 자체에서 첫 번째 변수를 사용하지 않고 (각 변수의 역할이보다 명확 해 지도록 세 번째 변수를 사용) 역전 된 첫 번째 노드 만 설정하는 것입니다 끝에 목록. 모두 그래서

모든 :

public void Reverse() { 
    Node current = Initial, previous = null; 
    while (current) { 
     Node next = current.Next; 
     current.Next = previous; 
     previous = current; 
     current = next; 
    } 
    Initial = previous; 
} 

Answer 2

하나의 해결책은 거꾸로 일 이전 노드 속성을 사용하여 다음 이중 연결리스트로 돌려 위해, 그리고 것 스스로 노력하지 마라.

Answer 3

당신이 재귀 적으로 수행 할 수

그런 다음 모든 개발자의 가치 하셨 지 2 펜스가 인식 할 것이다 "nreverse"또는 "현재 위치에서 역"을 호출하면

a->b->c->d 

    a->null 
    b->null 
     c->null 
     c<-d 
    b<-c 
    a<-b 

a<-b<-c<-d 

public void Reverse() 
{ 
    Reverse(Initial); 
} 

private void Reverse(Node node) 
{ 
    if(node != null && node.Next != null) 
    { 
     //go deeper 
     Reverse(node.Next); 
     //swap 
     node.Next.Next = node 
     node.Next = null; 
    } 
} 

Answer 4

그것은 해킹보다는 고전적인 알고리즘입니다.

철자가 틀린 변수의 이름을 바꾸는 것 외에는 유지 관리가 많이 필요하지 않습니다.

Answer 5

휠을 다시 시도하는 대신 확인해야합니다. 이미있는 경우 something from .Net Framework을 사용할 수 있습니다.

예를 들어 LinkedListNode으로 LinkedList을 입력합니다. 다른 경우에는 Queue 또는 Stack 일 수 있습니다.

Answer 6

다음 코드는 좀 더 직관적 수 있습니다 :

public void Reverse() 
{ 
    MyStack reverse = new MyStack(); 
    while (Initial != null) 
    { 
     reverse.Push(this.Pop()); 
    } 
    Initial = reverse.Initial; 
} 

은 (역은 MyStack 클래스의 멤버 방법입니다).

물론 원본 코드와 비교하여 두 배의 공간이 필요합니다.

Answer 7

stack s1 
s1.push_front(...) 
... 
s1.push_front(...) 

/////////////////////////////////////////////////////////////// pop_front 비어 요구에 :

void reverse(stack& to,stack_or_list& s) 
    while(!s.empty()){ 
     to.push_front(s.pop_front()); 
    } 
} 

/////////////

지금 to.pop_fronts의 시리즈는 당신이 필요로 stack_or_list

원하는 걸 얻을 수는 push_front, pop_front을