如何把链表相邻元素翻转

【腾讯笔试题】

题目描述：

把链表相邻元素翻转，例如给定链表为 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7，则翻转后的链表变为 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 7。

方法一：交换相邻两个结点的元素内容
这种方法是把相邻两个元素的data交换一下，这种方式应该不是面试官想要的。

def reverse1(link: SingleLink):
    left = right = link.head
    while left and left.next:
        right = left.next
        left.data, right.data = right.data, left.data
        left = right.next

方法二：交换相邻的结点
在设计交换结点的算法实现上，我们要考虑结点个数的问题。

def reverse(link: SingleLink):  # 1 2 3 4 5 6 7 8 9
    left = link.head  # 左  1
    pre = left
    right = left  # 考虑只有一个元素，倒数第二句不会出现 right is not define 错误
    if not left:  # 如果空链表
        return 

    while left and left.next:  # 这里考虑偶数个left最后是None
        right = left.next
        if left is link.head:  # 如果是前两个元素交换，考虑head
            link.head = right
        else:
            pre.next = right
        tmp = right.next    # 下面就没有head的事情了
        right.next = left
        left.next = tmp
        pre = left
        left = left.next
    if left:  # 奇数
        link.tail = left  # 尾巴也要处理一下
    else:
        link.tail = right.next
    return

测试：
构造一个单链表

# 构造一个单链表
遍历一遍，两个指针，
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class SingleLink:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, x):
        if self.head is None:
            self.tail = self.head = Node(x)
            return self
        self.tail.next = Node(x)
        self.tail = self.tail.next
        return self


ln = SingleLink()
for i in range(1, 9):
    ln.append(i)

调用两个函数：

print("反转前： ", end="")
p = ln.head
while p:
    print(p.data, end=" ")
    p = p.next

reverse1(ln)
print()
print("反转后： ", end="")
p = ln.head
while p:
    print(p.data, end=" ")
    p = p.next

print()
print("尾巴结点：", ln.tail.data)
反转前： 1 2 3 4 5 6 7 8 
反转后： 2 1 4 3 6 5 8 7 
尾巴结点： 7