你应该熟悉的链表

来源于 https://leetcode.com/tag/linked-list/
如果需要详细解释可以留言, 我会作图解释清楚点。

1. Reverse Linked List 翻转单链表

https://leetcode.com/problems/reverse-linked-list/description/

  • 解法1

思路:
1 2 3 4 5
1 3 2 4 5
1 4 3 2 5
1 5 4 3 2
5 4 3 2 1


class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if (head == None or head.next == None): return head
        q = None
        p = head.next
        while(p.next):
            q = p.next
            p.next = q.next
            q.next = head.next
            head.next = q
        # 环
        p.next = head
        head = p.next.next
        p.next.next = None
        return head

2. Merge Two Sorted Lists 合并两个排序链表

https://leetcode.com/problems/merge-two-sorted-lists/description/

思路: 保证 a是最小的, 然后递归合并b

class Solution:
    def mergeTwoLists(self, a, b):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not a or b and a.val > b.val:
            a, b = b, a
        if a:
            a.next = self.mergeTwoLists(a.next, b)
        return a

3. Remove Duplicates from Sorted List 从排序链表中去除重复元素

https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/

思路: 定义一个指针, 循环判断和 next是否相等, 注意 如果没有内while , 就处理不了 [1,2,2,2] 这样的情况.

def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p = head
        while p:
            while p.next and p.next.val == p.val:
                p.next = p.next.next
            p = p.next
        return head

4. Linked List Cycle 链表是否有环

https://leetcode.com/problems/linked-list-cycle/description/

思路: 定义两个指针, 一个走1步, 一个走2步,如果在结束前 二者相等, 就说明有环.

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None or head.next == None:
            return False
        slow = head.next
        fast = slow.next
        while slow and fast:
            if slow == fast:
                return True
            slow = slow.next
            fast = fast.next
            if fast:
                fast = fast.next
        return False

5. 是否回文

思路: 遍历丢到数组中, 然后while 判断首尾是否相等

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None or head.next == None: return True
        cache = []
        p = head
        while p:
            cache.append(p)
            p = p.next
        index = 0
        total = len(cache) // 2
        while index <= total :
            if cache[index].val != cache[len(cache) - index - 1].val:
                return False
            index += 1
        return True

6. Remove Linked List Elements 移除元素

https://leetcode.com/problems/remove-linked-list-elements/description/

思路: 递归即可, 如果相等 返回下一个;

func removeElements(head *ListNode, val int) *ListNode {
    if (head == nil) {
        return head
    }
    head.Next = removeElements(head.Next, val)
    if (head.Val == val) {
        return head.Next
    }
    return head
}

7. Intersection of Two Linked Lists 相交元素

https://leetcode.com/problems/intersection-of-two-linked-lists/

思路: 两个指针 分别指向头结点, 如果其中一个到末尾之后, 则求另一个

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA == None or headB == None: return None
        a = headA
        b = headB

        while a != b:
            a = headB if a == None else a.next
            b = headA if b == None else b.next
        return a

8. Add Two Numbers II 两个数字相加

https://leetcode.com/problems/add-two-numbers-ii/

思路: 有点bug, 先求两个链表的 val 转成 string 连在一起, 再把两个 string 转成 int 相加再转成int 就是结果, 然后构造链表

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        s1 = ''
        s2 = ''

        while l1:
            s1 += str(l1.val)
            l1 = l1.next
        while l2:
            s2 += str(l2.val)
            l2 = l2.next
        nums = str(int(s1) + int(s2))
        head = ListNode(0)
        p = head
        for i in range(len(nums)):
            p.next = ListNode(nums[i])
            p = p.next
        return head.next

9. Swap Nodes in Pairs 两两交换

https://leetcode.com/problems/swap-nodes-in-pairs/

思路:递归交换第一个和第二个

class Solution:
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None: return None
        if head.next == None: return head
        temp = head.next
        head.next = head.next.next
        temp.next = head
        head = temp
        head.next.next = self.swapPairs(head.next.next)
        return head