常用链表代码.md

@[toc]

链表小总结 (TODO)

代码

链表属性获取

1. 获取链表环入口

// 快慢指针法获取环入口
func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    // 判断链表是否有环
    loopFlag := false
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            loopFlag = true
            break
        }
    }
    // 表示链表无环
    if loopFlag == false {
        return nil
    }
    // 表示链表有环
    loopEntrance := head
    for loopEntrance != slow {
        loopEntrance = loopEntrance.Next
        slow = slow.Next
    }
    return loopEntrance
}

2. 获取两个链表相交节点

// 优雅解法
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    pA, pB := headA, headB
    for pA != pB {
        if pA == nil {
            pA = headB
        } else {
            pA = pA.Next
        }

        if pB == nil {
            pB = headA
        } else {
            pB = pB.Next
        }
    }
    return pA
}

3. 获取链表中点

// 双指针法
func middleNode(head *ListNode) *ListNode {
    if head == nil{
       return nil
    }
    slow, fast := head, head
    //  slow, fast := head, head        如果这样写的话，链表节点为偶数时，返回: 偏右的中间节点。
    //  slow, fast := head, head.Next	如果这样写的话，链表节点为偶数时，返回: 偏左的中间节点。
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

链表结构调整

1. 反转链表

// 迭代解法
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode = nil
    var next *ListNode = nil
    for head != nil {
        next = head.Next
        head.Next = pre
        pre = head
        head = next
    }
    return pre
}

// 递归解法
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

2. 删除链表倒数第n个节点

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil {
		return head
	}
	// 定义哑头节点，这样可以方便删除头节点时的处理
	dummyHead := &ListNode{-1, head}
	left, right := dummyHead, dummyHead
	for i := 0; i < n; i++ {
		right = right.Next
	}
	for right.Next != nil {
		right = right.Next
		left = left.Next
	}
	// 此时left指向了要删除节点的父节点
	left.Next = left.Next.Next
	return dummyHead.Next
}

3. 奇偶链表

328. 奇偶链表

// 一般解法，使用哑头节点
func oddEvenList(head *ListNode) *ListNode {
	oddDummyHead, evenDummyHead := &ListNode{-1, nil}, &ListNode{-1, nil}
	odd, even := oddDummyHead, evenDummyHead
	order := 1
	for head != nil {
		if order%2 == 1 {
			odd.Next = head
			odd = odd.Next
		} else {
			even.Next = head
			even = even.Next
		}
		head = head.Next
		order++
	}
	odd.Next = evenDummyHead.Next
	even.Next = nil // 记得清空
	return oddDummyHead.Next
}

// 不使用哑头节点 (官方解法)
func oddEvenList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	// odd为奇链表表头, even为偶链表表头
	odd, even, tmp := head, head.Next, head.Next
	for odd.Next != nil && even.Next != nil {
		odd.Next = even.Next
		odd = odd.Next
		even.Next = odd.Next
		even = even.Next
	}
	odd.Next = tmp
	return head
}

链表性质判断

1. 判断链表是否有环

141. 环形链表

// 哈希解法
func hasCycle(head *ListNode) bool {
    isVisited := make(map[*ListNode]int)
    for head != nil {
        if _, ok := isVisited[head]; ok {
            return true
        }
        isVisited[head] = 1
        head = head.Next
    }
    return false
}

// 双指针解法
func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

2. 判断链表是否回文

234. 回文链表

// 判断链表是否是回文链表  (解法1: 翻转前半部分) (比较复杂)
func isPalindrome(head *ListNode) bool {
	length := getLength(head)
	if length <= 1 {
		return true
	}
	mid := head
	for i := 0; i < length/2-1; i++ {
		mid = mid.Next
	}
	afterList := head
	if length%2 == 1 {
		afterList = mid.Next.Next
	} else {
		afterList = mid.Next
	}
	mid.Next = nil
	preList := reverse(head)
	return isSame(preList, afterList)
}

// 判断链表是否是回文链表  (解法2: 翻转后半部分) (相对简洁)
func isPalindrome(head *ListNode) bool {
	mid := getMid(head)
	preList := head
	afterList := reverse(mid)
	for preList != nil && afterList != nil {
		if preList.Val != afterList.Val {
			return false
		}
		preList = preList.Next
		afterList = afterList.Next
	}
	return true
}

// 获取链表中点，返回偏右的中心节点
func getMid(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

// 翻转链表，返回翻转后的头结点
func reverse(head *ListNode) *ListNode {
	var pre, next *ListNode = nil, nil
	for head != nil {
		next = head.Next
		head.Next = pre
		pre = head
		head = next
	}
	return pre
}

// 获取链表长度
func getLength(head *ListNode) int {
	length, cur := 0, head
	for cur != nil {
		cur = cur.Next
		length++
	}
	return length
}

// 判断两个链表是否相同
func isSame(listA, listB *ListNode) bool {
	for listA != nil && listB != nil {
		if listA.Val != listB.Val {
			return false
		}
		listA = listA.Next
		listB = listB.Next
	}
	return listA == listB
}

链表间关系判断

1. 判断两个链表是否相同

func isSame(listA, listB *ListNode) bool {
	for listA != nil && listB != nil {
		if listA.Val != listB.Val {
			return false
		}
		listA = listA.Next
		listB = listB.Next
	}
	return listA == listB
}

练习题

1. 属性获取
   • 142. 环形链表 II
   • 160. 相交链表
   • 876. 链表的中间结点
2. 性质判断
   • 141. 环形链表
   • 234. 回文链表
3. 结构调整
   • 19. 删除链表的倒数第N个节点
   • 92. 反转链表 II
   • 206. 反转链表
   • 328. 奇偶链表