Leetcode 线性表 Swap Nodes in Pairs

本文为senlie原创，转载请保留此地址：http://blog.****.net/zhengsenlie

Swap Nodes in Pairs

Total Accepted: 12511 Total
Submissions: 39302

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.

题意：交换给定链表中的相邻节点,但不能够改变链表里的值

如1->2->3->4交换后为2->1->4->3

思路：

按题意中的扫描去改变每两个相邻节点的next指针的指向就可以。

小技巧：

由于处理每两个相邻节点的时候，须要一个指针记录它们前一个节点，而头节点前面没有节点，

所以可设置一个dummy节点指向头指针，这样开头的两个节点的处理方式跟其他的相邻节点的处理方式就一样了

复杂度：时间O(n)，空间O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head){
    	if(!head) return NULL;
    	ListNode *dummy = new ListNode(0); dummy->next = head;
    	ListNode *pre = dummy, *cur = head, *next = head->next;
    	while(cur && next){
    		ListNode *temp = next->next;
    		pre->next = next;
    		cur->next = next->next;
    		next->next = cur;
    		pre = cur;
    		cur = temp;
    		next = temp==NULL ? NULL : temp->next;
    	}
    	return dummy->next;
    }