反转链表-精简实现

func reverseList(head *ListNode) *ListNode {
    var cur, prev *ListNode = head, nil
    for cur != nil {
        cur.Next, prev, cur = prev, cur, cur.Next
    }
    return prev
}

图解:

两两交换链表节点-精简实现

func swapPairs(head *ListNode) *ListNode {
    prev := &ListNode{Next:head}
    newHead := prev
    for prev.Next != nil && prev.Next.Next != nil {
        a := prev.Next
        b := a.Next
        prev.Next, b.Next, a.Next =b, a, b.Next
        prev = a
    }
    return newHead.Next
}

检测链表是否有环

解法:

• 一直遍历, 如果超时则有环
• 利用 map 记录访问过的节点
• 快慢指针

快慢指针解法:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for slow != nil && fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}