python算法-015将链表元素两两交换元素（交换值、就地翻转）

大鹏一日同风起，扶摇直上九万里。
假令风歇时下来，犹能簸却沧溟水。
世人见我恒殊调，闻余大言皆冷笑。
宣父犹能畏后生，丈夫未可轻年少。
——李白《上李邕》

在现代，别人对你的文章冷嘲热讽，你来一句：“你行你上啊！”他可能就没脾气了。但是要换李白，他真的会上，由于他真的行！

题目形容：将链表的每两个节点翻转。不允许用新的节点。
例如：
给定链表Head->1->2->3->4->5->7->7->8
反转为链Head->2->1->4->3->7->5->8->7

这题是为了明天的题目做铺垫的，先来分析下这个题：本质上还是操作链表，之前我们做过相似的。不过，这次是翻转节点，节点有两个属性data和next，交换两个节点的值即可以完成了，这样不需要将节点位置改变。这太简单了，就像a=1,b=2,交换a,b的值一样那么简单，只要要用一个中间值tmp来保存就行：tmp=a a=b b=tmp。主要的问题就是如何遍历的问题，这也是个不是问题的问题。用一个指针就可完成，但是对于明天的题，并没有太大帮助。

下面来看利用next属性，如何做：
利用next属性必然会改变节点的位置，也就是链表结构会变，先来看看怎么改变

主两个指针，更好了解

图中我用红笔标出了操作顺序1、2、3、4：先pre->fast，而后fast->slow，最后slow->next，这里为什么会先把next->fast.next:由于在第二步时，得保存后面的链表，不然会丢失，这与a.b交换值是一个道理。这里的顺序也可以换成1、2、4、3，两个效果是一样的。
这里有一个注意的地方就是每次的循环条件：主旨就是当后面的节点不够一组进行交换时，退出循环。但是如何知道后面不够一组呢？先来看下代码。
下面代码实现：

def function(head):    #判断链表能否为空，为空返回    if head.next is None or head.next.next is None:        return head    pre=head # 指向slow的前驱节点    slow=head.next    fast=slow.next    #slow和fast为相邻的节点    #next=fast.next    # 这里的循环条件要注意    # 链表的长度可能为奇数，也可能是偶数    # 每次四个指针会变换，由于是先操作再迭代下一组    # 再迭变换完后，假如fast指针后面只有一个元素，或者者没有元素，这时    # 后面的无法再进行翻转，所以应该出循环，正常应该做完在判断的，    # 这里只能符合的才操作，由于用的指针多了一个。    while fast.next is not None and fast.next.next is not None:        next = fast.next #保存链表，由于要断开        pre.next=fast        fast.next=slow        slow.next=next        # # 上面的四句做的操作，见图        pre=slow        slow=next        fast=slow.next    #由于面的判断条件，最后一组，我们并没有翻转，这里操作下    next = fast.next    pre.next = fast    fast.next = slow    slow.next = next    return head

这里我用while fast.next is not None and fast.next.next is not None，这一句看起来很臃肿。

一组
这里我用了四个指针，链表的长度可能为奇数，也可能是偶数，每次四个指针会变换，由于是先操作再迭代下一组，在变换完后，假如fast指针后面只有一个元素，或者者没有元素，这时后面的无法再进行翻转，所以应该出循环，按分析应该做完在判断的，但是由于涉及到一个next指针，每次都得确定还有next,才能操作，不然会报错，这里我还没找到一个好的解释办法。要注意的是，最后一组没有换位置，可以把最后的四行语句注释掉，看看结果就知道了。
image.png

鉴于此，我把指针减少了，只用一个主指针cur，用（cur，cur.next)这样一组来代替slow，fast。
这样的好处是，不用考虑fast能否有next.next,只看cur就行。操作是一样的：

image.png

代码实现：

def function(head):    if head is None or head.next is None:        return head    cur=head.next#当前遍历节点    pre=head#当前遍历节点的前驱节点    next=None#当前节点后继节点的后继节点    # 这里的循环条件可能不太一样，由于省掉了fast,所以考虑的东西就会变少。    while cur is not None and cur.next is not None:        next=cur.next.next        pre.next=cur.next        #这里可能一看不太好了解        # （cur.next).next        # 这样把cur.next看做一个节点，也就是之前的fast        cur.next.next=cur        cur.next=next        pre=cur        cur=next    return head

循环条件变了，我将他们放在一个文件里了，假如后者没问题，即可以把变换的链表变回去：

if __name__ == '__main__':    head = creatLink(6)    print("head:")    cur = head.next    while cur != None:        print(cur.data)        cur = cur.next    head = function_1(head)    print("\nAfterReverse_1:") # 这是用slow和fast的    cur = head.next    while cur != None:        print(cur.data)        cur = cur.next    head = function_2(head) # 这是cur    print("\nAfterReverse_2:")    cur = head.next    while cur != None:        print(cur.data)        cur = cur.next

输出结果：

image.png

一律代码：

import randomclass LNode:    def __init__(self,arg):        self.data=arg        self.next=None"""题目形容：给定链表Head->1->2->3->4->5->7->7->8反转为链Head->2->1->4->3->7->5->8->7要求：方法：只用一个cur,用pre和next辅助反转。"""def creatLink(x):    i = 1    head = LNode(None)    tmp = None    cur = head    while i <= x:        n = random.randint(1, 9)        tmp = LNode(n)        cur.next = tmp        cur = tmp        i += 1    return head##双指针法def function_1(head):    #判断链表能否为空，为空返回    if head.next is None or head.next.next is None:        return head    pre=head # 指向slow的前驱节点    slow=head.next    fast=slow.next    #slow和fast为相邻的节点    #next=fast.next    # 这里的循环条件要注意    # 链表的长度可能为奇数，也可能是偶数    # 每次四个指针会变换，由于是先操作再迭代下一组    # 再迭变换完后，假如fast指针后面只有一个元素，或者者没有元素，这时    # 后面的无法再进行翻转，所以应该出循环，正常应该做完在判断的，    # 这里只能符合的才操作，由于用的指针多了一个。    while fast.next is not None and fast.next.next is not None:        next = fast.next #保存链表，由于要断开        pre.next=fast        fast.next=slow        slow.next=next        # # 上面的四句做的操作，见图        pre=slow        slow=next        fast=slow.next    #由于面的判断条件，最后一组，我们并没有翻转，这里操作下    next = fast.next    pre.next = fast    fast.next = slow    slow.next = next    return headdef function_2(head):    if head is None or head.next is None:        return head    cur=head.next#当前遍历节点    pre=head#当前遍历节点的前驱节点    next=None#当前节点后继节点的后继节点    # 这里的循环条件可能不太一样，由于省掉了fast,所以考虑的东西就会变少。    while cur is not None and cur.next is not None:        next=cur.next.next        pre.next=cur.next        #这里可能一看不太好了解        # （cur.next).next        # 这样把cur.next看做一个节点，也就是之前的fast        cur.next.next=cur        cur.next=next        pre=cur        cur=next    return headif __name__ == '__main__':    head = creatLink(6)    print("head:")    cur = head.next    while cur != None:        print(cur.data)        cur = cur.next    head = function_1(head)    print("\nAfterReverse_1:")    cur = head.next    while cur != None:        print(cur.data)        cur = cur.next    head = function_2(head)    print("\nAfterReverse_2:")    cur = head.next    while cur != None:        print(cur.data)        cur = cur.next

铺垫就到这里，明天的题目是：
将链表以k个一组翻转，不足k个也翻转，
给定链表Head->1->2->3->4->5->7->7->8
k=3
反转为链Head->3->2->1->7->5->4->8->7
会吗？
今天就这样，更多题目见GitHub,简书、微信：DKider。
Data Knowledge idea(我成心打的r),这是我寒假想的名字，还挺好，之前没有什么实际意义，现在它有了！

我会尽量加快写的速度，我还要留时间学其余的知识。加油吧！