[go语言算法] 单链表反转

思路：单链表反转
Head -> Node1 -> Node2 -> Node3 -> Node4
如果将一个节点的next指针指向上一个节点，该节点与下一个节点的关系，引入变量tmp做临时存储。

pre <- cur  tmp->
         pre  tmp 
  
不停做替换直到最后一次将为nil的tmp赋值给cur判断为至。头指针注意最后一次指向非空prev，原因最后一次做了不符合条件的替换。

package main

import (
    "fmt"
)

type LNode struct {
    data int;
    next *LNode;
}

func main()  {
    Head := &LNode{}
    create(Head,10)
    node := Head.next;
    for i:=0;i<10 ;i++  {
        fmt.Println(node.data)
        node = node.next
    }

    reverseLinkList(Head)

    node = Head.next;
    for i:=0;i<10 ;i++  {
        fmt.Println(node.data)
        node = node.next
    }
}

func create(node *LNode,num int)  {
    for i:=0; i<num;i++  {
        newNode := LNode{i,nil}
        node.next = &newNode
        node = &newNode
    }
}

//Head       ->    node1   ->   node2   ->   node3
//
//
//Head  nil  <-    node1        node2   ->   node3
//    prev       cur          tmp
//                 |           |
//               prev         cur
//
//
//
//    nil  <-    node1   <-   node2        node3
//
//               prev          cur         tmp
//
//                             prev          cur


func reverseLinkList(Head *LNode)  {
    cur := Head.next
    Head.next = nil;  //可省略，循环体中会指向为nil的prev
    var prev *LNode
    var tmp *LNode
    for cur!=nil{
        tmp = cur.next
        cur.next=prev
        prev = cur
        cur = tmp
    }
    Head.next = prev;  
}

//递归法
func reverseList(head *ListNode) *ListNode {
    if(head.Next == nil){
        return head
    }
    p:= reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil  //避免尾部环 1->2->3->4->5           5->4->3->2->1->2->1
    return p    //返回尾节点
}