单链表逆置

单链表逆置的思路

a：将单链表储存为数组，然后按照数组的索引逆序进行反转。
b：使用3个指针遍历单链表，逐个链接点进行反转。
c：从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。
d: 递归(相信我们都熟悉的一点是，对于树的大部分问题，基本可以考虑用递归来解决。但是我们不太熟悉的一点是，对于单链表的一些问题，也可以使用递归。可以认为单链表是一颗永远只有左(右)子树的树，因此可以考虑用递归来解决。或者说，因为单链表本身的结构也有自相似的特点，所以可以考虑用递归来解决)

具体实现

pre指向前一个结点，cur指向当前结点，next指向下一个节点。

循环实现

class Node(object):
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next


# 使用for循环并不能生成链表
# for i in range(1,10):
#     link = Node(i)
link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))


def rev(link):
    pre = link
    cur = link.next
    pre.next = None
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    return pre


root = rev(link)
while root:
    print(root.data)
    root = root.next

递归实现

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


# 递归，head为原链表的头结点，newhead为反转后链表的头结点
def recurse(head, newhead):
    if head is None:
        return
    if head.next is None:
        newhead = head
    else:
        newhead = recurse(head.next, newhead)
        head.next.next = head
        head.next = None
    return newhead


# 建立链表1->2->3->4->None
head = ListNode(1)
p1 = ListNode(2)
p2 = ListNode(3)
p3 = ListNode(4)
head.next = p1
p1.next = p2
p2.next = p3
newhead = None

# 输出链表4->3->2->1->None
p = recurse(head, newhead)
while p:
    print(p.val)
    p = p.next

思路参考