【LeetCode】24. 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.

思路

遍历链表，每个值变化一下位置，同时需要保留这次的第二个值的指针以便下一轮更改指向。

代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==0) return head;
        ListNode* p = head;
        ListNode* q = head->next;
        ListNode* t =0;
        bool isInit = true;
        while(q) {
        	// 交换p、q
			swap(p, q);
			if(isInit) {
				head = q;
				isInit = false;
			}
			if(t){
				t->next=q;
				t = p;
			}
			else t = p;
			p = p->next;
			if(p) {
				q = p->next;
			} else {
				break;
			}
        }
        return head;
    }
    
    void swap(ListNode* p, ListNode* q) {
		p->next = q->next;
		q->next = p;
    }
};