# 引言
题目链接：https://leetcode.com/problems/swap-nodes-in-pairs/
# 题目大意
将链表中的节点两两交换。
- Example
Given 1->2->3->4, you should return the list as 2->1->4->3.
Hint:
Your algorithm should use only constant extra space.
You may not modify the values in the list's nodes, only nodes itself may be changed.
即不可采取交换节点的方式，同时保证空间复杂度为常数级别
# 题解
# 一句话题解
直接一张图说明，定义一个无效空头结点便于统一化操作
# 复杂度
时间复杂度 O(n)
空间复杂度 O(1)
# AC 代码
c++ 版本
/** | |
* 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) | |
{ | |
ListNode *ret = new ListNode(-1); | |
ret->next = head; | |
ListNode *pre = ret; | |
ListNode *cur = head; | |
while (nullptr != cur && nullptr != cur->next) | |
{ | |
pre->next = cur->next; | |
cur->next = pre->next->next; | |
pre->next->next = cur; | |
pre = cur; | |
cur = cur->next; | |
} | |
return ret->next; | |
} | |
}; |
go 版本
/** | |
* Definition for singly-linked list. | |
* type ListNode struct { | |
* Val int | |
* Next *ListNode | |
* } | |
*/ | |
func swapPairs(head *ListNode) *ListNode { | |
ret := &ListNode{-1, nil} | |
ret.Next = head | |
pre, cur := ret, head | |
for nil != cur && nil != cur.Next { | |
pre.Next = cur.Next | |
cur.Next = pre.Next.Next | |
pre.Next.Next = cur | |
pre = cur | |
cur = cur.Next | |
} | |
return ret.Next | |
} |
