[leetcode #24] Swap Nodes in Pairs

Problem

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

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

Example 2:

Input: head = []
Output: []

Example 3:

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

Constraints:

・ The number of nodes in the list is in the range [0, 100].
・ 0 <= Node.val <= 100

Idea

LinkedList의 노드 중 연속된 두 개의 노드를 쌍으로 볼 때 두 노드의 위치를 바꾸는 문제다.

위치를 바꾸는 작업을 완료한 후 head node를 리턴해야 하므로 head를 가리키는 노드를 만든다.

처음 head를 first 노드로, 그 다음 노드를 second 노드로 정한다. 루프를 돌면서 다음 쌍을 가리키는 노드를 임시로 저장한 뒤 first 노드와 second 노드가 가리키는 포인터를 변경한다. 두 노드의 위치를 변경한 뒤 prev 노드가 가리키는 노드를 변경이 완료된 후 첫 번째 노드를 가리키게 만든다. 그 뒤 first 노드와 second 노드를 다음 쌍을 가리키게 하면 된다.

Solution

/**
 * 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 swapPairs(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode first = head;
        ListNode second = first.next;
        ListNode origin = new ListNode();
        ListNode prev = origin;
        prev.next = first;

        while (first != null && second != null) {
            ListNode tmp = second.next;
            second.next = first;
            first.next = tmp;
            prev.next = second;
            prev = first;

            first = prev.next;
            if (first != null) {
                second = prev.next.next;
            } else {
                second = null;
            }
        }

        return origin.next;
    }
}

Reference

https://leetcode.com/problems/swap-nodes-in-pairs/