数据结构：单链表

链表的结构定义

单链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

从尾到头打印链表

使用递归的方法

func reversePrint(head *ListNode) []int {
   if head == nil {
       return nil
  }
  
   return appendData(head)
}

func appendData(head *ListNode) []int {
   if head.Next != nil{
       list := appendData(head.Next)
       list = append(list, head.Val)
       return list
  }

   return []int{head.Val}
}

使用栈进行辅助的方法

import "container/list"
func reversePrint(head *ListNode) []int {
	if head == nil {
		return nil
	}
	
	res := list.New()
	for head != nil {
		res.PushFront(head.Val)
		head = head.Next
	}
	
	ret := []int{}
	for e := res.Front(); e != nil; e = e.Next() {
		ret = append(ret, e.Value.(int))
	}
	
	return ret
}

反转单链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    var prev *ListNode
    cur := head

    for cur != nil {
        cur.Next, prev, cur = prev, cur, cur.Next
    }

    return prev
}

合并两个有序链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
		return list2
	}
    
	if list2 == nil {
		return list1
	}
    
	if list1.Val > list2.Val {
		list2.Next = mergeTwoLists(list1, list2.Next)
		return list2
	} else {
		list1.Next = mergeTwoLists(list1.Next, list2)
		return list1
	}
}