203.移除链表元素

题意：删除链表中等于给定值 val 的所有节点。

示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

示例 2： 输入：head = [], val = 1 输出：[]

示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]

思路：

  • 使用cur来遍历链表结点
  • 找到结点值为val的结点，对cur.next赋值为cur.next.next

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeElements(head, val):
        tem_head=ListNode(next=head)
        cur=tem_head
        while(cur.next!=None):
            if(cur.next.val==val):
                cur.next=cur.next.next
            else:
                cur=cur.next
        return tem_head.next

707.设计链表

题意：

在链表类中实现这些功能：

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class MyLinkedList(object):

    def __init__(self):
        self.head = Node()
        self.size = 0  # 设置一个链表长度的属性，便于后续操作，注意每次增和删的时候都要更新

    def get(self, index):
        """
        :type index: int
        :rtype: int
        """
        if index < 0 or index >= self.size:
            return -1
        cur = self.head.next
        while (index):
            cur = cur.next
            index -= 1
        return cur.val

    def addAtHead(self, val):
        """
        :type val: int
        :rtype: None
        """
        new_node = Node(val)
        new_node.next = self.head.next
        self.head.next = new_node
        self.size += 1

    def addAtTail(self, val):
        """
        :type val: int
        :rtype: None
        """
        new_node = Node(val)
        cur = self.head
        while (cur.next):
            cur = cur.next
        cur.next = new_node
        self.size += 1

    def addAtIndex(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """
        if index < 0:
            self.addAtHead(val)
            return
        elif index == self.size:
            self.addAtTail(val)
            return
        elif index > self.size:
            return

        node = Node(val)
        pre = self.head
        while (index):
            pre = pre.next
            index -= 1
        node.next = pre.next
        pre.next = node
        self.size += 1

    def deleteAtIndex(self, index):
        """
        :type index: int
        :rtype: None
        """
        if index < 0 or index >= self.size:
            return
        pre = self.head
        while (index):
            pre = pre.next
            index -= 1
        pre.next = pre.next.next
        self.size -= 1

206.反转链表

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

思路：

  • 首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
  • 然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
  • 为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
  • 接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
  • 最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。

代码：

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def reverseList(self, head):
        cur=head
        pre=None
        while(cur!=None):
            tmp=cur.next
            cur.next=pre
            pre=cur
            cur=tmp
        return pre

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

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

1
2
输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

1
2
输入：head = []
输出：[]

示例 3：

1
2
输入：head = [1]
输出：[1]

思路：

首先需要判断pre结点的下一个以及下下个不为None

cur定位pre.next，post定位pre.next.next

cur指向post.next，post指向cur，pre指向post

pre定位pre.next.next

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def swapPairs(self, head):
        res=ListNode(next=head)
        pre=res
        while pre.next!=None and pre.next.next!=None:
            cur=pre.next
            post=pre.next.next

            cur.next=post.next
            post.next=cur
            pre.next=post

            pre=pre.next.next
        return res.next

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

1
2
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

1
2
输入：head = [1], n = 1
输出：[]

示例 3：

1
2
输入：head = [1,2], n = 1
输出：[1]

思路：

  • 采用双指针的方法，首先快指针定位到位置n的结点
  • 其次快慢指针同时移动直到快指针移动到末尾此时慢指针在倒数第n个结点
  • 删除慢指针的结点

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def removeNthFromEnd( head, n):
        tmp=head
        fast=ListNode(next=head)
        slow=fast
        while(n!=0):
            n=n-1
            fast=fast.next
        while(fast.next):
            slow=slow.next
            fast=fast.next
        slow.next=slow.next.next
        return tmp

面试题 02.07. 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

img

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

img

1
2
3
4
5
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

img

1
2
3
4
5
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

img

1
2
3
4
5
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

思路：

  • 求两个链表的交点，主要就是求两个链表指针开始相等的地方
  • 两个链表相交 末尾的几个数值肯定相等
  • 定位到末尾的位置 依次前进判断是否有相等的

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def getIntersectionNode(self, headA, headB):
        lena,lenb=0,0
        cura,curb=headA,headB
        while cura:
            cura=cura.next
            lena+=1
        while curb:
            curb=curb.next
            lenb+=1
        if lena>lenb:
            lena,lenb=lenb,lena
            cura,curb=curb,cura
        n=lenb-lena
        while(n):
            curb=curb.next
            n-=1
        while cura:
            if cura==curb:
                return cura
            else:
                cura=cura.next
                curb=curb.next
        return None

142.环形链表II

题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

循环链表

思路：

  • 关键是通过计算 计算x和z之间的关系 假设在某个点相遇 以此产生的数学关系
  • 快指针以每次两步来移动，慢指针以每次一步来行动
  • 当产生快指针等于慢指针时，可以确定一定存在环
  • 假设起始位置到环起始点的距离为x，离环y距离为快慢指针的交点，距离环终点为z
  • 将p指向链表起始点，q指向两者的交点，同时移动每次一步，当p，q相交，交点为环的起始点
  • 公式为

$$
x = (n - 1) (y + z) + z
$$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def detectCycle(self, head):
        slow, fast = head, head #定义两个快慢指针
        while fast and fast.next:# 让快指针一直在跑
            slow = slow.next# slow走一步
            fast = fast.next.next# fast走两步
            # 如果相遇 也就是走到一点上 重新定义两个index 分别在起点和交点
            if slow == fast:
                p = head
                q = slow
                while p!=q:
                    p = p.next
                    q = q.next
                #你也可以return q
                return p
        return None