16-代码随想录206反转链表
206.反转链表
力扣题目链接(opens new window)
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
双指针+递归一起来
class ListNode:#定义一个节点def __init__(self,val=0,next=None):self.val=valself.next=next
class MyLinkList:def __init__(self):self.head=ListNodeself.size=0def initList(self,data):self.head=ListNode(data[0])r=self.headp=self.headfor i in data[1:]:node=ListNode(i)p.next=nodep=p.nextself.size+=1return rdef reverseList(self):#双指针法cur=self.headpre=Nonewhile(cur):temp=cur.nextcur.next=prepre=curcur=tempreturn predef reverseList1(self,cur1,pre1):#递归法if cur1==None:return pre1temp1=cur1.nextcur1.next=pre1return self.reverseList1(temp1,cur1)def printlist(self,head):#打印链表if head==None:returnnode=headwhile node!=None:print(node.val,end='')#在不换行的情况下打印节点（或元素）的值node=node.nextif __name__=='__main__':l=MyLinkList()data=input("输入链表:").split()if data==[]:print("[]")else:l1 = l.initList(data)l.printlist(l1)print('\n')print("反转成功后：", end='\n')pre = l.reverseList()l.printlist(pre)print('\n')print("再反转成功后：", end='\n')pre1 = l.reverseList1(pre, None)l.printlist(pre1)运行
小结
一定要注意递归的时候，每次再输入的值都在变，要在递归函数之外定义好初始值。然后可能要注意的就是打印链表是需要写链表函数的，它返回只有头指针，打印是要遍历再打印。还要注意的是打印函数里面输出设置为不换行，换行的话在主函数里自己写print就行。
