체인 테이블 반전 작업

체인 테이블 구조

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

이곳의 두결점도val값이 있는데, 그것은 빈 노드가 아니다.

해법 1 (귀속)

작동 시간: 31ms 사용 메모리: 688k

public class Solution {
    public ListNode ReverseList(ListNode head) {
         if(head==null || head.next==null){
               return head;
           }
        ListNode p=head.next;
        ListNode newHead=ReverseList(p);

        p.next = head;
        head.next =null;
        return newHead;
    }
}

전체 체인 시계를 두 개의 노드(두결점과 남은 노드)만 보고 나머지 노드의 꼬리 바늘만 두결점을 가리키고 두결점의 바늘은 공을 가리킨다.다시 남은 노드를 두 노드로 보고 순서대로 귀속시키면 된다.

해법2

실행 시간: 32ms 사용 메모리: 629k

import java.util.*;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }    
    Stack stack = new Stack();
        ListNode in = head;
        ListNode out = head;
        while(in!=null){
            stack.push(in.val);
            in = in.next;
        }
        while(out!=null){
            out.val = (int)stack.pop();
            out = out.next;
        }
        return head;
    }
}

체인 테이블의 구조와 바늘은 변하지 않습니다. 전체 체인 테이블의 값(val)을 반전하여 저장하면 됩니다(Stack 저장 값을 이용).

해법3

실행 시간: 29ms 사용 메모리: 629k

import java.util.*;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }    
        ListNode cur=head;
        ListNode pre=null;
        ListNode next=null;
        while(cur!=null)
            {
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}

체인 테이블의 값이 변하지 않고 중전 노드pre를 이용하여 바늘을 바꾸어 마지막 노드가 순서대로 첫 번째 노드를 가리키도록 한다.