24. Swap Nodes in Pairs 交换相邻的两个节

题目

给定一个链表，交换这个链表中两个响相邻的节点，并返回这个链表的头部，不要修改值，只能修改链表结构。（不提醒我还真没想到修改值也可以）

解析

1. 先不考虑边界问题

2. 需要 1 个游标 i ， 交换后两个节点 i +1 和 i+2 方便起见，保留下一个不动的节点 loc = i + 3

3. 交换 h+1 和 h+2，设置 p1 p2
   p2->Next = p1
   p1->Next = loc
   h.Next = p2

4. 移动 h = p1 loc = loc=2 移动时判断终止条件。

伪代码

vh.Next = head
h = vh
loc = h
for loc != nil && loc.Next != nil
    loc = loc.Next.Next
    swap(h.Next, h.Next.Next)
    move(h)

return vh.Next 

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    vh := &ListNode{}
    vh.Next = head
    loc := head
    head = vh
    var p1,p2 *ListNode
    for loc != nil && loc.Next != nil {
        loc = loc.Next.Next
        p1 = vh.Next
        p2 = p1.Next
        
        p2.Next = p1
        p1.Next = loc
        vh.Next = p2
        
        vh = p1
    }
    return head.Next
}

总结

1. 不能直接返回 head
2. 多用几个指针，没必要节约