24 两两交换链表中的节点.md

24、两两交换链表中的节点

题目：

两两交换链表中的节点，并且返回交换后的链表。不能单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例：

给定 1->2->3->4，应该返回2->1->4->3。

解法一（迭代）：

先把逻辑写清楚，然后写代码，这样一点也不难。

def swapPairs(head):
    
        point = ListNode(0)  #用来做循环的指针
        point.next = head    #把链表连接到point后面
        pre = point          #point会随着循环改变，pre用来返回值
        
        while point.next and point.next.next:
            
            #要交换的两个节点start和end
            start = point.next
            end = point.next.next
            
            #总共三条关系
            #A:temp指向start
            #B:start指向end
            #C:end指向下一个元素
            
            #改成如下的关系
            #AA:temp指向end
            #BB:end指向start
            #CC:start指向end.next
            
            #由于end.next带有后面链表信息，所以不能被首先覆盖
            point.next = end
            start.next = end.next
            end.next = start
            
            #更新point位置
            point = start
        
        return pre.next

解法二（递归）：

递归想清楚不容易，一点是从后往前执行，另外一点是自身调用自身。

根据迭代的解法，每两个节点需要改变三条关系，而递归从最后面开始，只需要改变两条关系。

def swapPairs(start):
        if start == None or start.next == None:
            return start
        else:
            end = start.next
            start.next = swapPairs(end.next)
            end.next = start 
            
        return end