1. 判断链表是否有环，如果有环找到环入口

思路：定义快、慢指针，从链表头开始，快指针每次走两步，慢指针每次走一步，如果相遇，说明有环。碰撞之后慢指针回到链表头部，快慢指针每次走一步，第一次相遇就是环入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func getLinkCircle(head *Node) *Node {<!-- -->
    fast := head
    last := head
    cur := head
    for cur != nil && cur.Next != nil {<!-- -->
        last = last.Next
        fast = fast.Next.Next
        if last == fast {<!-- --> // 第一次相遇
            break
        }
        cur = cur.Next
    }
    // 没有环
    if fast == nil || last == nil {<!-- -->
        return nil
    }
    last = head
    for last != fast {<!-- -->
        last = last.Next
        fast = fast.Next
    }
    return last
}

2. 在一次选举投票中，有一个候选人的投票超过了50%，在选票中找出这个候选人。

思路：投票法，定义两个变量，一个记录当前候选人编号，一个记录候选人票数。遍历，遇到相同的编号计数加1，不同的减1，为0时，更换候选人编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func getMaxVoteNum(arr []int) int {<!-- -->
    major := arr[0]
    count := 0
    for i := 0; i < len(arr); i++ {<!-- -->
        if major == arr[i] {<!-- -->
            count++
        } else {<!-- -->
            if count == 0 {<!-- -->
                major = arr[i]
                count++
            } else {<!-- -->
                count--
            }
        }
    }
    return major
}