type LikedList struct{
Val int
Next *LikedList
}
// 头插法，倒置单链表
func reverseLikedList(head *LikedList)*LikedList{
if(head == nil || head.Next == nil){
return head
}
var pre, next *LikedList
// head是当前节点，pre是当前节点的前一个几点，next是当前节点的后一个节点
for head != nil { // 当前节点不为空
next = head.Next // 备份head.Next（指向当前节点的下一个节点），防止移动节点时找不到后置节点
head.Next = pre // 更新head.Next，后一个节点指向前一个（翻转）
pre = head // 前一个节点后移
head = next // 当前节点后移
}
return pre // 注意：当pre指向原链表的最后一个节点时，head已经指向最后一个节点的Next即空节点，所以这里应返回pre
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, m int, n int) *ListNode {
changeLen := n - m 1 // 计算需要逆置的节点个数
var pre *ListNode = nil // 初始化开始逆置的节点的前驱
var result *ListNode = head // 最终转换后的链表的头结点，非特殊情况即为head
move := m - 1 // head向后移动m-1个位置指向第m个节点
for(head != nil && move > 0){ // 将head后移m-1个位置，即
pre = head // for循环后pre指向第m个节点的前驱节点
head = head.Next // for循环后head指向第m个节点
move--
}
var reversedListTail *ListNode = head // 此时reversedListTail指向的是第m个节点，该节点即是链表片段反转后的尾节点
var reversedListHead *ListNode = nil // 记录链表片段反转后的头结点
for(head != nil && changeLen > 0){ // 逆置changeLen个节点
next := head.Next // 暂存当前节点的下一个节点
head.Next = reversedListHead // 当前节点的Next指针域指向新开辟的反转后的头结点
reversedListHead = head // 反转后的链表的头结点后移一个位置
head = next // 当前节点后移一个节点
changeLen-- // 每完成一个节点逆置，changLen--
}
reversedListTail.Next = head // 连接逆置后的链表尾与逆置段的后一个节点，翻转后的尾节点指向第n个节点的下一个节点
if(pre != nil){ // 如果pre不为空，说明不是从第1个节点开始逆置的，即m > 1
pre.Next = reversedListHead // 将逆置链表开始的节点前驱与逆置后的头结点连接起来
}else{ // 如果pre为空，说明m=1，即从第1个节点开始逆置，结果即为逆置后的头结点
result = reversedListHead
}
return result
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
var lenA, lenB int // 分别记录链表headA和链表headB的长度
lenA = getListLength(headA)
lenB = getListLength(headB)
if lenA > lenB {
headA = forwardDeltaLenNode(lenA, lenB, headA) // headA链表的头结点指向移动多出的节点个位置后
}else{
headB = forwardDeltaLenNode(lenB, lenA, headB) // 如果链表headB长，移动其头结点到相应位置
}
for headA != nil && headB != nil { // 没有到达链表末尾
if(headA == headB){ // 当前两个链表的节点相同，即指向同一个节点，说明找到的交点；否则，两链表同时后移
return headA
}
headA = headA.Next
headB = headB.Next
}
return nil // 遍历到链表末尾还没有找到同一个节点，说明两链表没有交点
}
// 逐个节点遍历，获取链表长度
func getListLength(head *ListNode)int{
var lengthList int
for head != nil {
lengthList
head = head.Next
}
return lengthList
}
// 较长链表移动 长链表长度-短链表长度 个节点后对应的头指针
// 参数longLen和shortLen分别表示长链表和短链表的长度，longList对应长链表
func forwardDeltaLenNode(longLen, shortLen int, longList *ListNode)*ListNode{
deltaLen := longLen - shortLen
for longList != nil && deltaLen != 0{
longList = longList.Next
deltaLen--
}
return longList // 如果longList为nil或者deltaLen=0直接返回此时的头结点longList
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func partition(head *ListNode, x int) *ListNode {
//var preHead, postHead *ListNode // 前后两部分链表的头结点，不能这么声明，这样声明的话两者都为&ListNode{0, nil}其中Next域为nil，当运行到prePtr.Next = head时会报panic: runtime error:invalid memory address or nil pointer deference错误
preHead := &ListNode{0, nil} // 生成一个preHead链表的头结点，该节点固定一直不对其移动，改头节点的Val为多少都不影响结果，因为使用的是头结点的Next节点
postHead := &ListNode{0, nil} // 生成一个postHead链表的头结点，该节点固定不动
prePtr := preHead // prePtr指针对preHead链表进行遍历，注意：开始时其指向preHead
postPtr := postHead
for head != nil { // 遍历原链表
if(head.Val < x ){ // 小于x的节点尾插到preHead链表后面
prePtr.Next = head // prePtr的Next域指向当前节点，即将当前节点从preHead链表尾部prePtr依次插入
prePtr = head // prePtr指针后移一位，指向当前节点
}else{ // 大于等于x的节点放在postHead链表的后面
postPtr.Next = head // 将当前节点插入到postHead链表尾节点postPtr后面
postPtr = head // postHead链表的尾节点后移一位
}
head = head.Next // 当前指针后移一位
}
// 对head链表遍历结束分为preHead和postHead两个子链表
prePtr.Next = postHead.Next // 注意：这里是将preHead链表的尾节点prePtr的Next域指向postHead链表头结点的下一个节点
postPtr.Next = nil // postPtr的尾节点的Next域指向空
return preHead.Next // 返回preHead链表的Next之后的链表
}
END 十期推荐 【251期】面试官：谈谈你对零拷贝的理解~ 【252期】运行时常量池的一道面试题（JDK8环境） 【253期】面试官：熟悉Docker操作吗？说几个常用的Docker命令吧 【254期】面试官：来谈谈微服务组件Feign的工作原理吧 【255期】面试官：Mybatis是如何运用设计模式的？ 【256期】面试官常考的 21 条 Linux 命令 【257期】面试官：谈谈你对Java线程安全与不安全的理解 【258期】今日头条的面试题：LRU原理和Redis实现 【259期】面试官：Spring事务失效的场景有哪些？如何解决？ 【260期】Java线程池，这篇能让你和面试官聊了半小时 ？ ~