美文网首页剑指offer-python
面试16:链表反转

面试16:链表反转

作者: fighting_css | 来源:发表于2018-06-24 16:28 被阅读0次

    【题目描述】
    输入一个链表,反转链表后,输出新链表的表头。
    【思路】
    采用三个节点,cur为当前需要反转节点,pre为cur之前反转好的节点,pos为下一步将要反转的节点。
    例如:
    链表 1->2-> 3-> 4 ->5 ->None
    第一次循环
    循环前:
    pre = None
    cur = 1
    pos = 2
    循环后:
    None <-1 2-> 3 ->4 ->5-> None
    pre = None 1
    cur = 2
    pos = 3
    第二次循环后:
    None <-1<- 2 3->4->5->None
    依次循环
    当pos==None时
    pre = None <-1<- 2 <-3 <-4
    cur = 5
    执行cur.next = pre即可
    【代码】

    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        # 返回ListNode
        def ReverseList(self, pHead):
            # write code here
            if pHead == None or pHead.next == None:
                return pHead
            #当前节点
            cur = pHead
            pre = None
            pos = pHead.next
            while pos!=None:
                cur.next = pre
                pre = cur
                cur = pos
                pos = pos.next
            cur.next = pre
            return cur
    

    相关文章

      网友评论

        本文标题:面试16:链表反转

        本文链接:https://www.haomeiwen.com/subject/gnqsyftx.html