反转链表

需要考虑空链表，只有一个结点的链表

def reverse_link(head):
    if not head or not head.next:
        return head
    then = head.next
    head.next = None
    last = then.next
    while then:
        then.next = head
        head = then
        then = last
        if then:
            last = then.next
    return head


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


class Nodes(object):
    def __init__(self, values=None):
        self.nodes = self._set_link(values) if values else None

    def get_link(self):
        return self.nodes

    def print_self(self):
        Nodes.print_link(self.nodes)

    @staticmethod
    def print_link(link=None):
        count = 1
        while link:
            if count == 1:
                print (link.val),
            elif count % 5 == 0:
                print (link.val)
            else:
                print(link.val) ,
            count += 1
            link = link.next


    def _set_link(self, values):
        head = ListNode(0)
        move = head
        try:
            for val in values:
                tmp = ListNode(val)
                move.next = tmp
                move = move.next
        except Exception as e:
            print (e)
        return head.next


if __name__ == '__main__':
    nodes = Nodes([7, 8, 9])
    link = nodes.get_link()
    nodes.print_self()
    head = reverse_link(link)
    nodes.nodes = head
    Nodes.print_link(head)
    nodes.print_self()

结果展示：

7
8
9
9
8
7
9
8
7

————————————————————————————————————————————————————————————————————————————

从尾到头打印单链表

思路1：使用栈 思路2：递归

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


class Link(object):

    @staticmethod
    def link(values):
        head = ListNode(0)
        move = head
        try:
            for val in values:
                tmp = ListNode(val)
                move.next = tmp
                move = move.next
        except Exception as e:
            print (e)
        return head.next


def print_links(links):
    stack = []
    while links:
        stack.append(links.val)
        links = links.next
    while stack:
        print (stack.pop())


def print_link_recursion(links):
    if links:
        print_link_recursion(links.next)
        print (links.val)


if __name__ == '__main__':
    head = Link.link([1, 2, 3, 4, 5, 6])
    print_link_recursion(head)

结果展示：

6
5
4
3
2
1

——————————————————————————————————————————————————————————————————

复杂链表的复制

链表中除了指向后一个结点的指针之外，还有一个指针指向任意结点

分为三步完成：

一.复制每个结点，并把新结点放在老结点后面，如1->2,复制为1->1->2->2

二.为每个新结点设置other指针

三.把复制后的结点链表拆开

import random


class Node(object):

    def __init__(self, val):
        self.val = val
        self.next = None
        self.other = None


class Solution(object):

    @staticmethod
    def clone_nodes(head):
        # 结点复制
        move = head
        while move:
            tmp = Node(move.val)
            tmp.next = move.next
            move.next = tmp
            move = tmp.next
        return head

    @staticmethod
    def set_nodes(head):
        # other指针设置
        move = head
        while move:
            m_next = move.next
            if move.other:
                m_next.other = move.other.next
            move = m_next.next
        return head

    @staticmethod
    def reconstruct_nodes(head):
        # 结点拆分
        ret = head.next if head else Node
        move = ret
        while head:
            head = move.next
            if head:
                move.next = head.next
                move = move.next
        return ret

    @staticmethod
    def clone_link(head):
        # 结果
        h = Solution.clone_nodes(head)
        h = Solution.set_nodes(h)
        ret = Solution.reconstruct_nodes(h)
        return ret

    @staticmethod
    def print_nodes(head):
        # 打印结点值，结点other的值，用来比较
        ret = []
        while head:
            tmp = [head.val]
            if head.other:
                tmp.append(head.other.val)
            ret.append(tmp)
            head = head.next
        print(ret)

    @staticmethod
    def construct_nodes(vals):
        """
        构造一个简单的复杂链表
        :param vals: list
        :return: Nodes
        """
        if not vals:
            return Node
        move = head = Node(vals.pop(0))
        nodes = [None, head]
        for v in vals:
            tmp = Node(v)
            move.next = tmp
            nodes.append(tmp)
            move = move.next
        # print [node.val for node in nodes if node]
        move = head
        while move:
            # 设置other指针为随机结点
            move.other = random.choice(nodes)
            move = move.next
        return head


if __name__ == '__main__':
    link = Solution.construct_nodes([1, 3, 5, 7, 9])
    Solution.print_nodes(link)
    test = Solution.clone_link(link)  # 复制
    Solution.print_nodes(test)

结果展示：

[[1, 1], [3], [5, 1], [7, 3], [9]]
[[1, 1], [3], [5, 1], [7, 3], [9]]