Gidhub BE Developer

LeetCode : 206. Reverse Linked List

2020-11-14
goodGid
LeetCode

206. Reverse Linked List

Problem

Reverse a singly linked list.

Example

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

[1] Code (20. 11. 14)

public ListNode reverseList(ListNode head) {
    if (head == null) {
        return head;
    }

    ListNode toBeCurrent = head.next;
    ListNode toBePrev = head;
    toBePrev.next = null;

    while (toBeCurrent != null) {
        ListNode temp = toBeCurrent.next;
        toBeCurrent.next = toBePrev;
        toBePrev = toBeCurrent;
        toBeCurrent = temp;
    }

    return toBePrev;
}
  • 재밌었다.

[2] Code (21. 08. 15)

Need to Retry

public ListNode reverseList(ListNode head) {

    ListNode first = null;
    ListNode second = null;
    ListNode third = null;

    if (head == null) {
        return null;
    }
    first = head;

    if (first.next == null) {
        return first;
    }
    second = first.next;
    first.next = null;

    if (second.next == null) {
        second.next = first;
        return second;
    }
    third = second.next;

    while (third != null) {
        second.next = first;
        first = second;
        second = third;
        third = second.next;
    }

    second.next = first;

    return second;
}

  • 25분가량 소요

  • 깔끔하게 풀 수 있을 텐데 생각이 들었는데 떠오르지 않아서

    일단 머릿속에 아이디어를 구현했고 맞췄다.

  • 다시 풀어봐도 좋을 문제라고 생각이 들었다.

  • 다른 코드를 봤는데 굉장히 깔끔한 코드가 있었다.

    참고하도록 하자 !

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    while(current != null) {
        ListNode temp = current.next;
        current.next = prev;
        prev = current;
        current = temp;
    }
    return prev;
}

[3] Code (21. 10. 10)

Need to Retry -> 자료구조를 사용해보자.

public ListNode reverseList(ListNode head) {
    
    ListNode l = null;
    ListNode r = null;
    ListNode m = head;
    
    while (m != null) {
        r = m.next;
        m.next = l;
        l = m;
        m = r;
    }
    return l;
}

Reference Code

public ListNode reverseList(ListNode head) {
    
    //declare Stack
    //for each node
    //  put node in stack
    
    //take first node from stack
    //while stack is not empty
    //. node .next = stack.pop
    //return first Node
    
    if(head == null){
        return null;
    }
    
    Stack<ListNode> nodes = new Stack<>();
    ListNode cur = head;
    nodes.push(cur);
    while(cur != null){
            if(cur.next != null){
                nodes.push(cur.next);
            }
        cur = cur.next;          
    }
    
    ListNode returnNode = nodes.pop();
    ListNode headTemp = returnNode;
    while(nodes.size() != 0){
        headTemp.next = nodes.pop();
        headTemp = headTemp.next;
    }
    headTemp.next = null;
    
    return returnNode;
}

  • Stack을 사용하면 자연스럽게 Reverse하게 연결을 할 수가 있다.

    굉장히 좋은 접근이라는 생각이 든다.

FeedBack

  • Iteratively 하게 풀었다.

    다른 코드를 보니 Stack을 사용했는데 너무 좋은 접근이었다.

    다음엔 Stack 자료구조를 떠올려서 풀어보면 좋을 거 같다.

Reference

Recommend

Index