019.单链表反转

时间限制：10.000S  空间限制：128MB

题目描述 §

根据一个整数序列构造一个单链表，然后将其反转。

例如：原单链表为 2 3 4 5 ，反转之后为5 4 3 2

输入描述 §

输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开

输出描述 §

针对每组测试数据，输出包括两行，分别是反转前和反转后的链表元素，用空格隔开

如果链表为空，则只输出一行，list is empty

输入示例 §

5 1 2 3 4 5 
0

输出示例 §

1 2 3 4 5 
5 4 3 2 1 
list is empty

提示信息 §

本题用数组，也是可有过的，输入一遍数组，然后倒叙输出。不过建议大家用本题来链表操作

答案 §

注意：本题一次读取一行数据时，要把缓冲区加大，因为测试数据会有一行很长的情况

package main
 
import (
    "bufio"
    "os"
    "fmt"
    "strings"
    "strconv"
)
 
var (
    line []byte
    err error
    n int
    arr []string
)
 
func main() {
    reader := bufio.NewReaderSize(os.Stdin, 1024 * 1024)
    for {
        line, _, err = reader.ReadLine()
        if err != nil {
            break
        }
        arr = strings.Fields(string(line))
        n, _ = strconv.Atoi(arr[0])
        if n == 0 {
            fmt.Println("list is empty")
            continue
        }
        arr = arr[1:n + 1]
        dummy := &LinkedListNode{}
        cur := dummy
        for _, str := range arr {
            cur.Next = &LinkedListNode{ Val: str }
            cur = cur.Next
        }
        printLinkedList(dummy.Next)
        dummy.Next = reverseLinkedList(dummy.Next)
        printLinkedList(dummy.Next)
    }
}
 
type LinkedListNode struct {
    Val string
    Next *LinkedListNode
}
 
func printLinkedList(head *LinkedListNode) {
    cur := head
    for cur.Next != nil { // 题目保证了链表长度大于 0
        fmt.Printf("%s ", cur.Val)
        cur = cur.Next
    }
    fmt.Printf("%s\n", cur.Val)
}
 
func reverseLinkedList(head *LinkedListNode) *LinkedListNode {
    var (
        cur = head
        prev *LinkedListNode
        next *LinkedListNode
    )
 
    for cur != nil {
        next = cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
 
    return prev
}