# 链表

### [实现链表的排序](https://leetcode.com/problems/sort-list/)

 使用`O(n logn)`的时间复杂度对链表进行排序

```go
/* 链表排序
 * 1、每一个节点是一个有序链表，当前节点与排好序的链表进行合并
 * 2、合并两个有序链表，只需要两个当前指针进行比大小即可
 * 3、O(n logn) 需要进行分治，合并是O(n), 分治才能0(log n)
 * 4、两个快慢指针，快指针跳两下，慢指针跳一下，达到对半分治的效果
 */
func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil { return head }
    
	slow, fast := head, head
	var prev *ListNode

	for fast != nil && fast.Next != nil {  // fast 比 slow 快一倍，即 slow 是半点
		prev = slow
		slow = slow.Next
		fast = fast.Next.Next
	}
	prev.Next = nil

	l1 := sortList(head)
	l2 := sortList(slow)
    return mergeTwoLists(l1,l2)
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    var tmp = &ListNode{}
    var head = tmp
    for l1!=nil && l2!=nil{
        if(l1.Val < l2.Val){
            tmp.Next = l1
            l1 = l1.Next
            tmp = tmp.Next
        }else{
            tmp.Next = l2
            l2 = l2.Next
            tmp = tmp.Next
        }
    }
    if(l1 != nil){
        tmp.Next = l1
    }else if(l2 != nil){
        tmp.Next = l2
    }
    return head.Next
}

```

### 实现高效的单向链表逆序输出

```go
// 如何实现一个高效的单向链表逆序输出？
import "fmt"

type node struct {
	data int
	next *node
}

func reverse(head *node) {
	if head == nil || head.next == nil {
		return
	}
	var prev *node
	var next *node
	pcur := head
	for pcur != nil {
		if pcur.next == nil { //此时为最后一个节点
			pcur.next = prev
			break
		}
		next = pcur.next //取下一个节点
		pcur.next = prev // 将当前节点挂在下一个节点 (pcur) 的后面
		prev = pcur      // 当前节点
		pcur = next      //将下一个节点指给 pcur
	}
	tmp := pcur
	for tmp != nil {
		fmt.Print(tmp.data, " ")
		tmp = tmp.next
	}
}
func main() {
	var head *node = &node{data: 0, next: nil} //指针指向资源区
	var varHead *node = head
	fmt.Println("before:")
	for i := 1; i < 6; i++ { // 构建链表
		var tmp node = node{data: i, next: nil}
		fmt.Print(tmp.data, " ")
		varHead.next = &tmp
		varHead = varHead.next
	}
	fmt.Println()
	fmt.Println("after:")
	reverse(head)
}
```