leetcode : Reverse Linked List

public ListNode reverseList(ListNode head){
		Stack<ListNode> stack = new Stack<ListNode>();
		ListNode result = new ListNode(0);
		ListNode node = head;
		while(node != null) {
			stack.add(node);
			node = node.next;
		}
        
		if(stack.empty()) return null;
		
        node = stack.pop();

		result.next = node;
		while(!stack.empty()) {
			ListNode popedNode = stack.pop();
			node.next = popedNode;
			node = node.next;
			
		}
		node.next = null;
		return result.next;
	}

 

재귀를 이용하여 깔끔하게 정리

 

public ListNode reverseList(ListNode head) throws EmptyStackException {
		if(head == null || head.next == null) 
			return head;
		
		ListNode nextNode = head.next;
		ListNode newHead = reverseList(nextNode);
		nextNode.next = head;
		head.next = null;
		return newHead;
	}

nextNode를 이용해 바라보는 방향을 바꿔줍니다.

nextNode(3)을 head(2)를 보게 하고

 

head.next = null로 2가 보는 방향을 없애 줍니다.

head.next = null은 역순으로 바꿔줄 때 꼬리 부분이 보는 곳을

null로 만들어줍니다.

 

newHead는 반환하는 노드 리스트입니다.

newHead는 마지막에 결과를 전달해주는 역할 뿐입니다.

관련 부분을 삭제해도 역순으로 바꾸는 것에 영향은 없습니다.