[LeetCode] 206. Reverse Linked List

Problem

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution

Logic

1. 연결 리스트 내에 헤드 이전 노드(Left), 헤드 노드, 헤드 다음 노드(Right) 총 3개의 노드를 가리키는 포인터를 선언한다.

2. 헤드 노드가 참조하는 다음 노드를 헤드 이전 노드(Left)로 변경한다.

3. 헤드 이전 노드(Left)가 헤드 노드를 가리키도록 하고, 헤드 노드는 헤드 다음 노드(Right)를 가리키도록하고, 헤드 다음 노드(Right)는 본 노드의 다음 노드를 가리키도록 한다.

4. 2번과 3번 과정을 반복한다.

   Code

   /**
    * 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) {
        if (head == null) return null;
        ListNode left = null, right = head.next;
        while (right != null) {
            head.next = left;
            left = head;
            head = right;
            right = right.next;
        } head.next = left;
        return head;
    }
   }
   

   Time Complexity

   • 연결 리스트의 길이를 n이라 가정했을 때, 코드의 수행 시간을 좌우하는 것은 while반복문의 n번 계산 횟수이다. 따라서 본 솔루션은 O(n)의 시간 복잡도를 가진다.