leetcode-链表类题型

xuthus5

2019-04-17 (Updated: 2025-01-01 )

interview

algorithm,

1. 链表反转

来源：Leetcode 206

方法一：迭代法(头节点插入法)

思路：创建一个节点dummy，总是用来标识一个新的链表的头节点，把源链表每一次循环脱落的节点，添加到dummy.Next中，最后新建的链表就是反转后的链表

func reverseList(head *ListNode) *ListNode {
    var dummy = &ListNode{}
    var next = &ListNode{}
    for head!= nil {
        next = head.Next
        head.Next = dummy.Next
        dummy.Next = head
        head = next
    }
    return dummy.Next	//dummy指向的下一个节点开始才是真正的链表反转值
}
//执行用时 : 4 ms, 在Reverse Linked List的Go提交中击败了91.80% 的用户
//内存消耗 : 2.6 MB, 在Reverse Linked List的Go提交中击败了53.21% 的用户

方法二：迭代法-就地反转

思路：把当前节点的下一个节点插入到dummy的下一个节点，就地反转

func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    var dummy = &ListNode{Val:-1,Next:head}
    var prev = head
    var next = head.Next
    for next != nil {
        prev.Next = next.Next
        next.Next = dummy.Next
        dummy.Next = next
        next = prev.Next
    }
    return dummy.Next
}
//执行用时 : 4 ms, 在Reverse Linked List的Go提交中击败了91.80% 的用户
//内存消耗 : 2.6 MB, 在Reverse Linked List的Go提交中击败了52.52% 的用户

2. 查找链表中间节点

来源：Leetcode 876

方法：快慢指针法

思路：设置两个指针slow,fast，分别标识快慢指针，每一次slow前进一个节点，fast都将双倍速度前进。则fast到链表末尾时，slow处于中间位置

func middleNode(head *ListNode) *ListNode {
    var fast,slow *ListNode
	fast,slow = head,head
	for fast != nil {
        if fast.Next != nil {
            fast = fast.Next.Next
		    slow = slow.Next
        }else{
            break
        }
	}
    return slow
}
//执行用时 : 0 ms, 在Middle of the Linked List的Go提交中击败了100.00% 的用户
//内存消耗 : 2 MB, 在Middle of the Linked List的Go提交中击败了40.00% 的用户

3. 查找链表倒数第 k 个结点

来源：Leetcode 19

方法：间隔指针法

思路：设置指针ahead,rear，分别标识处于前方和后方的指针，两者间隔k，故当ahead到达链表末尾，rear处于K节点位置，删除rear即可

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    var dummy = &ListNode{-1,head}
    var ahead,rear = dummy,dummy
    //ahead先行n个单位
    for i:=0;i<n;i++{
        if ahead != nil {
            ahead = ahead.Next
        }else{
            break
        }
    }
    //ahead和rear同步
    for ahead.Next != nil {
        ahead = ahead.Next
        rear = rear.Next
    }
	//删除节点
    rear.Next = rear.Next.Next
    return dummy.Next
}
//执行用时 : 4 ms, 在Remove Nth Node From End of List的Go提交中击败了93.49% 的用户
//内存消耗 : 2.2 MB, 在Remove Nth Node From End of List的Go提交中击败了87.56% 的用户

4. 逆序打印链表

来源：牛客网-《剑指Offer》第3题

名称：从尾到头打印链表

题目内容：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList

方法：递归

思路：简单的递归思想，直接深入到链表末尾，然后输出

func printListFromTailToHead(head *ListNode) []int {
    var arr []int
    if head == nil {
        return nil
    }
    res := printListFromTailToHead(head.Next)
    arr = append(arr,res...)
    return arr
}

5. 判断一个链表是否有环

来源：Leetcode 141

方法一：map映射法

思路：将链表节点的地址作为键名，写入map，每一次判断键名是否存在，若存在，则必定在该点闭合成环

func hasCycle(head *ListNode) bool {
    var list = make(map[*ListNode]int)
    var cp = head
    for cp != nil {
        //判断是否已经经过该点
        if v,ok := list[cp];!ok {
            //没有经过
            list[cp] = v
            cp = cp.Next
        }else {
            //经过了，表明已经闭合
            return true
        }
    }
    return false
}
//执行用时 : 20 ms, 在Linked List Cycle的Go提交中击败了26.34% 的用户
//内存消耗 : 6.4 MB, 在Linked List Cycle的Go提交中击败了5.40% 的用户

方法一：快慢指针法

思路：将链表节点的地址作为键名，写入map，每一次判断键名是否存在，若存在，则必定在该点闭合成环

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    var fast,slow = head,head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            return true
        }
    }
    return false
}
//执行用时 : 12 ms, 在Linked List Cycle的Go提交中击败了94.44% 的用户
//内存消耗 : 4 MB, 在Linked List Cycle的Go提交中击败了30.16% 的用户

6. 相交链表

来源：Leetcode 160

方法一：map映射

思路：定义类型 map[*ListNode]int 键名存储节点的地址，第一次循环将headA的节点地址写入map中，第二次遍历headB时，直接判断map中是否存在节点地址，存在则输出。

复杂度：O(n) 时间复杂度，O(n) 空间复杂度

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    //利用map
    var ma = make(map[*ListNode]int)
    var a = headA
    //地址写入
    for a != nil {
        ma[a] = a.Val
        a = a.Next
    }
    //判断
    var b = headB
    for b != nil {
        if _,ok := ma[b];ok{
            return b
        }else{
            b = b.Next
        }
    }
    return nil
}
//执行用时 : 96 ms, 在Intersection of Two Linked Lists的Go提交中击败了30.84% 的用户
//内存消耗 : 6.4 MB, 在Intersection of Two Linked Lists的Go提交中击败了86.94% 的用户

7. 合并两个有序链表

来源：Leetcode 21

方法一：递归合并

思路：新建一个节点dummy用来标识某一个最小的链表头，每一次递归新生成的dummy的 Next 都等于再次递归生成的dummy

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //递归返回条件
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    
    var dummy = &ListNode{}
    if l1.Val < l2.Val {
        dummy = l1
        dummy.Next = mergeTwoLists(l1.Next,l2)
    }else {
        dummy = l2
        dummy.Next = mergeTwoLists(l1,l2.Next)
    }
    return dummy
}
//执行用时 : 4 ms, 在Merge Two Sorted Lists的Go提交中击败了98.69% 的用户
//内存消耗 : 2.6 MB, 在Merge Two Sorted Lists的Go提交中击败了21.53% 的用户

方法二：循环合并

思路：定义一个浮动节点dummy来指定每一次l1和l2比较后返回的节点，定义一个head节点标识dummy浮动的头部，每次都将dummy.Next指向l1和l2比较后的小者，后浮动dummy指向下一个节点，依次循环

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //循环合并
    var dummy = &ListNode{}
    var head = dummy
    for l1 !=nil && l2 != nil {
        if l1.Val <= l2.Val {
            dummy.Next = l1
            l1 = l1.Next
        }else {
            dummy.Next = l2
            l2 = l2.Next
        }
        dummy = dummy.Next
    }
    if l1 == nil {
        dummy.Next = l2
    }else {
        dummy.Next = l1
    }
    return head.Next
}
//执行用时 : 8 ms, 在Merge Two Sorted Lists的Go提交中击败了50.58% 的用户
//内存消耗 : 2.5 MB, 在Merge Two Sorted Lists的Go提交中击败了93.30% 的用户

8. 请判断一个链表是否为回文链表

来源：Leetcode 234 《回文链表》

方法一：container/list模拟栈操作

思路：获取链表长度，链表前半部分入栈，后半部分与出栈元素比较

复杂度：O(n) 时间复杂度，O(n) 空间复杂度

func isPalindrome(head *ListNode) bool {
    //特殊情况
    if head == nil || head.Next == nil {
        return true
    }
    //用栈 list模拟栈 前半段入栈
    var stk = list.New()
    //获得长度 快慢指针法
    var slow,fast = head,head
    stk.PushBack(slow.Val)
    //指针开始浮动
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        stk.PushBack(slow.Val)
    }
    stk.Remove(stk.Back())
    var cp = slow
    //奇数个节点 调整
    if fast != nil {
        cp = cp.Next
    }
    //出栈元素开始与链表后半部分比较
    for cp != nil {
        if stk.Back().Value != cp.Val {
            //不匹配 直接返回
            return false
        }else {
            //匹配，消项处理
            stk.Remove(stk.Back())
            cp = cp.Next
        }
    }
    return true
}
//执行用时 : 28 ms, 在Palindrome Linked List的Go提交中击败了69.44% 的用户
//内存消耗 : 6.1 MB, 在Palindrome Linked List的Go提交中击败了58.20% 的用户

方法二：快慢双指针+链表反转

思路：用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题。需要用到双指针+链表反转，反正我们上面已经知道了如何反转链表，和利用快慢指针进行链表操作。将慢指针指向链表中央，往后的链表节点反转，再从头开始，比对链表头节点和中央往后的节点。

func isPalindrome(head *ListNode) bool {
    //特殊情况
    if head == nil || head.Next == nil {
        return true
    }
    //指定快慢指针
    var slow,fast = head,head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    //备份中间节点
    var cp,comp = slow,slow
    //链表反转
    if fast != nil {
        //奇数长度的链表 往后错位一个
        cp = cp.Next
    }
    var dummy = &ListNode{}
    var next = &ListNode{}
    for cp != nil {
        next = cp.Next
        cp.Next = dummy.Next
        dummy.Next = cp
        cp = next
    }
    //反转完毕，开始比对
    dummy = dummy.Next
    for head != comp {
        if head.Val != dummy.Val {
            return false
        }else {
            head = head.Next
            dummy = dummy.Next
        }
    }
    return true
}
//执行用时 : 24 ms, 在Palindrome Linked List的Go提交中击败了96.11% 的用户
//内存消耗 : 6.1 MB, 在Palindrome Linked List的Go提交中击败了58.20% 的用户

方法三：数组

思路：将所有节点值压入数组，比较索引i与len()-1-i的大小

func isPalindrome(head *ListNode) bool {
	s := make([]int, 0, 100)
	for {
		if head == nil {
			break
		}
		s = append(s, head.Val)
		head = head.Next
	}
	for i := 0; i < len(s)/2; i++ {
		if s[i] != s[len(s)-1-i] {
			return false
		}
	}
	return true
}

9. 删除排序链表中的重复元素

来源：Leetcode 83

方法：前后比较法

思路：定义一个间隔指针pre指向当前操作节点的前面

func deleteDuplicates(head *ListNode) *ListNode {
    //只有一个元素或空链表
    if head == nil || head.Next == nil {
        return head
    }
    var pre,node = head,head.Next
    var dummy = pre
    //开始比对删除元素
    for node != nil {
        if pre.Val == node.Val {
            node = node.Next
            pre.Next = node
        }else {
            pre = node
            node = node.Next
        }
    }
    return dummy
}
//执行用时 : 8 ms, 在Remove Duplicates from Sorted List的Go提交中击败了93.24% 的用户
//内存消耗 : 3.1 MB, 在Remove Duplicates from Sorted List的Go提交中击败了59.12% 的用户

参考

链表常见题型整理