单链表反转

leetcode 206 https://leetcode-cn.com/problems/reverse-linked-list

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
 
示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:

输入:head = [1,2]
输出:[2,1]
示例 3:

输入:head = []
输出:[]

提示:

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

要反转链表,首先想到的是链表的头节点将会变尾节点,链表是通过指针将一个个节点连接起来的,那么可以选择改变指针指向,反转过程中,假设当前操作的节点为pNow,那么要改变当前节点指向的下一个节点,必须先记录下当前几点的下一个节点,不然改变指针后,导致下一个节点找不到,使得链表断链,所以还需要一个pNext指针,指向当前节点的下一个节点。另外,本来当前节点pNow的指针指向下一个节点,现在要反转,那就是要将当前节点的指针指向它的前一个节点,所以,也需要一个指针记录pPre前一个节点。

接下来分析操作步骤,首先当前要操作的节点从链表的头节点开始,先记录下一个节点,即pNext = pNow.next,接下来反转当前节点的指针指向前一个节点,即pNow.next = pPre,改变完指针后,记录当前节点的前一个节点,用来处理下一个节点的时候指向这个节点,即pPre = pNow,继续操作下一个节点,即pNow = pNext,操作结束的标志是当前链表已经到末尾了,也就是最后一个节点已经处理完了,即pNow == nil,然后返回pPre即为反转后链表的头节点。

在leetcode用go代码实现如下:
`/**

  • Definition for singly-linked list.

  • type ListNode struct {

  • Val int
    
  • Next *ListNode
    
  • }
    */
    func reverseList(head *ListNode) *ListNode {
    var pNow *ListNode = head
    var pPre *ListNode = nil
    var pNext *ListNode

    for pNow != nil {
    pNext = pNow.Next
    pNow.Next = pPre
    pPre = pNow
    pNow = pNext
    }

    return pPre
    }`

原文地址:https://www.cnblogs.com/kks170716/p/15339803.html