[파이썬 알고리즘 인터뷰] 역순 연결 리스트

(15) 역순 연결리스트

★ Easy

github.com/onlybooks/algorithm-interview

 

[LeetCode]

---

 

Reverse Linked List - LeetCode

1. 풀이법

 1-1. 재귀

 

파이썬

 

onlybooks/algorithm-interview

 

자바

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverse(ListNode node, ListNode prev){
        if(node == null)
            return prev;
        ListNode next = node.next;
        node.next = prev;
        return reverse(next, node);
    }
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }
}

속도차이 증말 으마으마 하당..

 1-2. while

이게 더 직관적인 방법같긴한데 포인터가 여러개니까 좀 햇갈리는 것 같기도하다.

파이썬

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None
        
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
        
        return prev
            

 

자바

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode node = head, prev = null;
        
        while(node != null){
            ListNode next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        
        return prev;
    }
}

 

재귀는 그냥 next랑 prev 계속 교차하는거고 while의 전체 흐름은 아래와같다. 포인터를 계속 옮겨가면서 node.next의 방향을 변경해주는 것

 

차그차근 보자면 아래와 같이 4단계로 이루어진다.