[Leetcode] 206. Reverse Linked List

Identifying the Problem

Linked List를 뒤집어 리턴한다.

Organizing thoughts

풀이 아이디어는 크게 두 가지가 떠올랐다.

1) linked list를 진행하면서 각 node의 값을 배열에 저장하고, 다시 진행하면서 거꾸로 값을 집어넣는 것이다.
   이렇게 되면 시간 복잡도 O(2n) 이 될 것이고, int val이 아니라 다른 멤버 변수가 있다면 더 복잡해진다.

2) linked list를 진행하고난 후 이전 노드가 그 이전 노드를 가리키게 하는 것이다.

 

2안이 깔끔해서 2안으로 풀이해보았다.

pre_pre, pre, head가 한 칸씩 이동하면서 node->next를 수정한다고 이해하면 될 것 같다.

주소	A	B	C	D	E
변수	pre_pre	pre	head
value	NULL	1	2	3	NULL
node-> next		B->A	C->B	D->C	break

 

 

Sourcecode

struct ListNode* reverseList(struct ListNode* head)
{
    
    if(!head) return NULL;
    
    struct ListNode* pre_pre = NULL;
    struct ListNode* pre = head;
    head = head->next;
    
    while(1)
    {
        pre->next = pre_pre;
        pre_pre = pre;
        pre = head;
        
        if(head)
            head = head->next;
        else break;
    }
    
    

     
    return pre_pre;
}

Mistake

• linked list 가 처음부터 NULL 인 경우를 생각 못함
• return시 pre는 NULL이므로 pre_pre를 리턴했어야했다.