清风徐来
0%

发表于 分类于

Remove Nth Node From End of List

No.19

Given the head of a linked list, remove the nth node from the end of the list and return its head.

解题思路：需要移除倒数第N个节点，只需要找到n-1个节点x，将x.next指向x.next.next即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func removeNthFromEnd(head *ListNode, n int) *ListNode {
  t := &ListNode{0, head}
	p, c := t, t
	for n > 0 && p != nil {
		p = p.Next
		n--
	}
	if p == nil {
		return nil
	}
  // 这里需要注意 不能多走
	for p.Next != nil {
		p = p.Next
		c = c.Next
	}
	c.Next = c.Next.Next
	return t.Next
}

Linked List Cycle

No.141

Given head, the head of a linked list, determine if the linked list has a cycle in it.

1
2
3
4
5
6
7
8
9
10
11
func hasCycle(head *ListNode) bool {
    t1 := head
	for head != nil && head.Next != nil {
		head = head.Next.Next
		t1 = t1.Next
		if head == t1 {
			return true
		}
	}
	return false
}

Intersection of Two Linked Lists

No.160

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

还有另外两种解法1.找出长度差，然后让长链表从到终点与短链表长度一致处出发，循环判断 2.把链表连接起来，寻找环的起点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func getIntersectionNode(headA, headB *ListNode) *ListNode {
  h1, h2 := headA, headB
	for h1 != h2 {
		if h1 == nil {
			h1 = headB
		} else {
			h1 = h1.Next
		}

		if h2 == nil {
			h2 = headA
		} else {
			h2 = h2.Next
		}
	}
	return h1
}

发表于 更新于 分类于

Merge Two Sorted Lists

No.21

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    r := &ListNode{0, nil}
	head := r
	for {
		if list1 == nil {
			r.Next = list2
			break
		}
		if list2 == nil {
			r.Next = list1
			break
		}
		if list1.Val > list2.Val {
			r.Next = list2
			list2 = list2.Next
		} else {
			r.Next = list1
			list1 = list1.Next
		}
		r = r.Next
	}
	return head.Next
}

Merge k Sorted Lists

No.23

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	r := &ListNode{0, nil}
	head := r
	for {
		if list1 == nil {
			r.Next = list2
			break
		}
		if list2 == nil {
			r.Next = list1
			break
		}
		if list1.Val > list2.Val {
			r.Next = list2
			list2 = list2.Next
		} else {
			r.Next = list1
			list1 = list1.Next
		}
		r = r.Next
	}
	return head.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
	len := len(lists)
	if len == 0 {
		return nil
	}
	if len == 1 {
		return lists[0]
	}
	mid := len / 2
	left := mergeKLists(lists[:mid])
	right := mergeKLists(lists[mid:])
	return mergeTwoLists(left, right)
}

分割链表

No.86

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置

这个题读题就挺困惑，解题思路：根据x将链表拆分为两个链表，一个存储小于x的值，另一个存其它值，最后再将其合并即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func partition(head *ListNode, x int) *ListNode {
	big := &ListNode{0, nil}
	less := &ListNode{0, nil}
	th := head
	nh := less
	var temp *ListNode
	for th != nil {
		if th.Val >= x {
			big.Next = th
			big = big.Next
		} else {
			less.Next = th
			less = less.Next
		}
		temp = th
		th = th.Next
		temp.Next = nil
	}
	less.Next = big.Next
	return nh.Next
}

发表于 分类于

在编程中，我们很多时候需要自定义错误处理。但是由于go本身的一些语法特性，存在着一个问题。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
type MyError struct {
	msg    string // 错误描述
	Offset int64  // 错误发生的位置
}

func (e *MyError) Error() string {
	return e.msg
}

func noThorwError() error {
	var err *MyError
	if 1 == 2 {
		err = &MyError{msg: "错误", Offset: 12}
	}
	return err
}

func main() {
	err := noThorwError()
  // 这里始终是true
	if err != nil {
		fmt.Println("发生异常")
	}
}

上面的代码，调用noThorwError() 始终引发异常，究其原因，是因为在golang中，interface{}类型实

际上由(T,V)两部分构成，直接调用nil进行判断时，T==MyError 而不是nil引发。

这块可以参考：https://go.dev/doc/faq#nil_error

具体解决办法如下：

  1. 错误类型仅对包内可见 只对外暴露构造方法 这样可以避免在方法申明中被使用
  2. 方法申明中错误类型使用error
  3. 方法内部不通过var err *myError这种方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 错误类型仅对包内可见 只对外暴露构造方法 这样可以避免在方法申明中被使用
type myError struct {
	msg    string // 错误描述
	Offset int64  // 错误发生的位置
}

func (e *myError) Error() string {
	return e.msg
}

// 函数返回值类型申明为error
func noThorwError() error {
	if 1 == 2 {
		return getErr
	}
	return nil
}

func main() {
	err := noThorwError()
	if err != nil {
		fmt.Println("发生异常")
	}
	fmt.Println(reflect.TypeOf(err))
}

发表于 分类于 ，

浅析 Mybatis 缓存

Mybatis 缓存分为一级缓存和二级缓存两种。

一级缓存：属于 SqlSession 级别缓存，同一个 SqlSession 下的同一个查询会被缓存。qlSession 去执行 commit 操作（执行插入、更新、删除），清空 SqlSession 中的一级缓存。执行 close 操作，会执行 cache = null；

二级缓存：属于 Mapper 级，针对同一 Mapper 下不同的操作都会缓存。