python实现单链表的反转

递归实现

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


def recurse(head, newhead):  # 递归，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

if __name__ == '__main__':

    head = ListNode(1)  # 测试代码
    p1 = ListNode(2)  # 建立链表1->2->3->4->None
    p2 = ListNode(3)
    p3 = ListNode(4)

    head.next = p1
    p1.next = p2
    p2.next = p3
    newhead = None

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

迭代方法，通过声明一个头指针进行节点与节点之间的链接

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


def reverseList(head):
    if head == None or head.next == None:  # 若链表为空或者仅一个数就直接返回
        return head
    pre = None
    while (head != None):
        next = head.next  # 1
        head.next = pre  # 2
        pre = head  # 3
        head = next  # 4
    return pre


if __name__ == '__main__':
    l1 = Node(1)  # 建立链表3->2->1->9->None
    l1.next = Node(2)
    l1.next.next = Node(3)
    l1.next.next.next = Node(4)
    l = reverseList(l1)
    print(l1)
    print(l)
    print (l.elem, l.next.elem, l.next.next.elem, l.next.next.next.elem)

"""
def reverse1(head):
    if head is None or head.next is None:
        return head
    current = head
    pre = None
    pnext = None
    while current is not None:
        pnext = current.next
        current.next = pre
        pre = current
        current = pnext

    return pre
"""