剑指offer–反转链表

一、前言

最近开始刷剑指offer，记录一下。牛客网在线编程板块的剑指offer专区。

牛客网剑指offer：传送门

或者点击下方链接。

https://www.nowcoder.com/ta/coding-interviews

二、题目描述

输入一个链表，反转链表后，输出新链表的表头。

三、代码

# -*- coding:utf-8 -*-
# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        # 1、将现有的头换成尾，尾部的next为空
        # 2、将从第二个node开始，循环将next指向前一个
        # 3、需要一直有一个指针指向还没有翻转的链表的头部
        if pHead==None:
            return None
        if pHead.next==None:
            return pHead

        leftPoint = pHead
        midPoint = pHead.next
        # rightPoint = pHead.next.next
        rightPoint = midPoint.next
        leftPoint.next = None

        while rightPoint != None:
            midPoint.next=leftPoint
            leftPoint=midPoint
            midPoint=rightPoint
            rightPoint=rightPoint.next
        midPoint.next = leftPoint
        return midPoint
if __name__ == '__main__':
    s=Solution()
    l1 = ListNode(1)
    l2 = ListNode(2)
    l3 = ListNode(3)
    l4 = ListNode(4)
    l5 = ListNode(5)
    l1.next = l2
    l2.next = l3
    l3.next = l4
    l4.next = l5
    l5.next = None

    print(s.ReverseList(l1))