LeetCode_24: Swap Nodes in Pairs

# 引言

题目链接：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
}