LeetCode Swap Nodes in Pairs: Using Sentinel Header

Overview

The LeetCode Swap Nodes in Pairs problem itself is not difficult, and using a sentinel header could make the code more compact and shorter and thus is a plus.

LeetCode Swap Nodes in Pairs Problem

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Solution to adopt sentinel header

Simple test on your ability to handle pointers. Keep several pointers as you want (I guess just two pointers are not enough) and simulate the required process, be careful about some special case and NULL pointers. One plus by using a sentinel header, i.e., make a fake node and use it as the header of the linked list could make it much easier and more consistent to do some pointer manipulation, the following code is accepted by LeetCode OJ to pass this Swap Nodes in Pairs problem:

ListNode *swapPairs(ListNode *head) {
    if (NULL == head || NULL == head->next) return head;
    ListNode sentinel(0);
    sentinel.next = head->next;
    ListNode *ptrCurr = head;
    ListNode *ptrNext = head->next;
    ListNode *ptrTail = &sentinel;  
    while (ptrCurr && ptrCurr->next) {
        ptrNext = ptrCurr->next; 
        ptrTail->next = ptrNext;
        ptrTail = ptrCurr;
        ptrCurr->next = ptrNext->next;
        ptrNext->next = ptrCurr;
        ptrCurr = ptrCurr->next;
    }
    return sentinel.next;
}

Summary

The LeetCode Swap Nodes in Pairs problem itself is not difficult, and using a sentinel header could make the code more compact and shorter and thus is a plus.

Written on April 27, 2013