[leetcode] Swap Nodes in Pairs

Swap Nodes in Pairs

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.

Tag: linked list






 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
class Solution {
    ListNode *swapPairs(ListNode *head) {
        ListNode * p = head;
        ListNode * q = NULL;
        /*handle empty input*/
        if (head == NULL || head->next == NULL){
            return head;
        /*handle first two nodes*/
        head = p->next;
        p->next = head->next;
        head->next = p;
         * line 34: p is the last node of previous swapped pair
         * line 35: set q to the fist node of current pair
         * line 36: link p->next to the second node of current pair
         * line 37: move p to the second node of current pair
         * line 38: link q->next to the first node of next pair
         * line 39: link p->next to the first node of current pair (q)
         * line 40: set p to the second node of current swapped pair
        while (p->next != NULL && p->next->next != NULL){ //judge from left to right
            q = p->next;
            p->next = q->next;
            p = p->next;
            q->next = p->next;
            p->next = q;
            p = q;
        return head;



Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.