[LeetCode#206] Reverse Linked List

❒ Description

---

제목	Reverse Linked List
링크	https://leetcode.com/problems/reverse-linked-list/
자료구조	선형 (연결리스트)

 

이번 문제는 연결리스트를 뒤집는 방법에 대해 알 수 있는 문제다.

기억해두면 쓸모가 있을 듯.

 

 

 

❒ Solve

---

1.  재귀 구조

public ListNode reverse(ListNode node, ListNode prev) {
    if (node == null) {
    	return prev;
    }
    ListNode next = node.next;
    node.next = prev;
    return reverse(next, node);
}

 

`1 → 2 → 3`를 reverse 하는 케이스

1st	2nd	3rd	4th
node = node(1) prev = null	node = node(2) prev = node(1)	node = node(3) prev = node(2)	node = null prev = node(3)
next = node(2)	next = node(3)	next = null
node.next = null	node.next = node(1)	node.next = node(2)
reverse(node(2), node(1)) ↗	reverse(node(3), node(2)) ↗	reverse(null, node(3)) ↗
return node(3)	← return node(3)	← return node(3)	← return node(3)

 

 

 

2.  반복 구조로 뒤집기

public ListNode reverse(ListNode node) {
    ListNode prev = null;
    ListNode current = node;
    
    while(node != null) {
    	ListNode next = node.next;
        currnet.next = prev; 
        prev = node;
        current = next;
    }
    return prev;
}