链表.md

链表

链表基础理论

206. 反转链表

1.空指针法

func reverseList(head *ListNode) *ListNode {
    if head==nil{
        return nil
    }
    if head.Next==nil{
      return head
    }
    cur:=head
    var pre *ListNode
    
    for cur!=nil{
        tmp := cur.Next
        cur.Next=pre
        pre=cur
        cur=tmp
    }

    return pre
}

2.递归法

func reverse(head *ListNode) *ListNode {
	if head==nil || head.Next==nil{
		return head
	}
	last :=reverse(head.Next)
	head.Next.Next=head
	head.Next=nil
	return last
}

142. 环形链表 II

Hash 法

    LMap:=map[*ListNode]int{}
    for head!=nil{
        if _,ok:=LMap[head];ok{
            return head
        }
        LMap[head]++
        head=head.Next
    }
    return nil

92. 反转链表 II

反转前N个节点、反转m到n之间的节点

var pre *ListNode
func reverseN(head *ListNode,n int) *ListNode {
	
    
	if n == 1{
		pre =head.Next
		return head
	}
	last :=reverseN(head.Next,n-1)
	head.Next.Next=head
	head.Next = pre
	return last
}

func reverseBetween(head *ListNode,m,n int) *ListNode {

	if m == 1{
		return reverseN(head,n)
	}

	head.Next = reverseBetween(head.Next,m-1,n-1)
	return head
}

25. K 个一组翻转链表

func reverseAtoB(a,b *ListNode) *ListNode {
	var pre *ListNode
	cur :=a
	nxt :=a
	for cur !=b{
		nxt=cur.Next
		cur.Next=pre
		pre =cur
		cur=nxt
	}
	return pre
}

func reverseKGroup(head *ListNode, k int) *ListNode {
   if head ==nil{
   	return nil
   }
	a :=head
	b:=head
	for i := 0; i <k ; i++ {
		if b==nil{
			return head
		}
		b = b.Next
	}
	newHead:=reverseAtoB(a,b)
   a.Next=reverseKGroup(b,k)
   return newHead
}