资讯详情

24. 两两交换链表中的节点

思路：一次移动两个单位，然后交换两个节点，感觉不难。

注意的点：注意交换节点时候的顺序。

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func swapPairs(head *ListNode) *ListNode {if head == nil{return nil}dummyHead := &ListNode{Next : nil,}dummyHead.Next = headcur := dummyHeadfor cur != nil && cur.Next != nil && cur.Next.Next != nil{secound := cur.Next.Nextfirst := cur.Nextfirst.Next = secound.Nextsecound.Next = firstcur.Next = secoundcur = cur.Nextcur = cur.Next}return dummyHead.Next
}

　　

19.删除链表的倒数第N个节点

思路：第一次遍历记录到链表size，然后用size - n 得到要移动的距离，最后进行节点操作，不难

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {size := 0dummyHead := &ListNode{Val :-999,Next : head,}cur := dummyHeadfor cur!= nil && cur.Next != nil{size++cur = cur.Next}loop := size - ncur = dummyHeadfor cur!=nil && cur.Next !=nil && loop > 0 {loop--cur = cur.Next}cur.Next = cur.Next.Nextreturn dummyHead.Next
}

　　

面试题 02.07. 链表相交

思路：用哈希表，记录之前的链表是否出现过，很简单。

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {cur := headAhash := map[*ListNode]int{}for cur != nil {hash[cur]++cur = cur.Next}cur = headBfor cur != nil{if hash[cur] == 1{return cur}hash[cur]++cur = cur.Next}return nil
}

　　

142.环形链表II

思路：用哈希表，统计节点出现的次数。

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func detectCycle(head *ListNode) *ListNode {hash := map[*ListNode]int{}cur := headfor cur != nil {if hash[cur] == 1{return cur}hash[cur]++cur = cur.Next}return nil
}