移除链表元素

题目描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

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

思路解析

此题考查链表的删除操作，设置一个虚拟头节点指向第一个节点，这样就可以统一删除操作了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* removeElements(ListNode* head, int val) {
        ListNode* hn = new ListNode(0,head);
        // 通过虚拟节点的方式实现删除操作
        for (ListNode* tn = hn; tn && tn->next; tn=tn->next)
        {
            while (tn->next && tn->next->val == val)
            {
                ListNode* dn = tn->next;
                tn->next = tn->next->next;
                delete dn;
            }
        }
        return hn->next;
    }

需要注意for循环里的判断条件tn && tn->next，当while循环执行完毕时tn->next可能会是nullptr，这时for循环会执行tn = tn->next，使得tn变为nullptr，所以这时需要判断tn是否为nullptr。除了这种特殊情况是用tn来判断，其他都是用tn->next来判断是否结束循环。

设计链表

题目描述

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

  • MyLinkedList() 初始化 MyLinkedList 对象。
  • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
  • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
  • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
  • void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

思路解析

这题考查对链表的底层理解和实现，为了操作简便我们设置了一个虚拟头节点，这个头节点指向链表的第一个节点，这样无论输入链表是不是空，类属性head都存在。

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
class MyLinkedList {
public:
    struct ListNode{
        int val;
        ListNode* next;
        ListNode(int v):val(v),next(nullptr){}
    };
    
    MyLinkedList() {
        head = new ListNode(0);
        sz = 0; 
    }
    
    int get(int index) {
        if (sz == 0 || index < 0  || index >= sz)  return -1;
        ListNode* tn;
        int i;
        for (i = 0,tn = head->next; i < index;i++, tn=tn->next);
        return tn->val;
    }
    
    void addAtHead(int val) {
        ListNode* nn = new ListNode(val);
        nn->next = head->next;
        head->next = nn;
        sz++;
    }
    
    void addAtTail(int val) {
        ListNode* nn = new ListNode(val);
        ListNode* tn;
        for (tn = head; tn->next; tn=tn->next);
        tn->next = nn;
        sz++;
    }
    
    void addAtIndex(int index, int val) {
        if (index < 0 || index > sz)   return;
        ListNode* tn = head;
        for (int i = 0; i < index; i++, tn=tn->next);
        ListNode* nn = new ListNode(val);
        nn->next = tn->next;
        tn->next = nn;
        sz++;
    }
        

    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= sz)   return;
        ListNode* tn = head;
        for (int i = 0; i < index; i++, tn=tn->next);
        ListNode* dn = tn->next;
        tn->next = tn->next->next;
        delete dn;
        sz--;
    }
private:
    ListNode* head;
    int sz;
};

需要注意的是addAtIndex方法的边界判断，当index == size时表示在整个链表末尾加元素，这点和deleteAtIndex是不同的。

反转链表

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

思路解析

这题是典型的双指针题型，需要设置一前一后指针，前指针是遍历指针，用来倒转next指针指向，后指针是用来记录倒转指针指向位置的，此外还需要设置一个局部临时指针变量，这个指针的作用是暂存前指针原先的next指针，让遍历得以完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode *reverseList(ListNode *head)
    {
        if (!head)  return nullptr;
        ListNode* fp = head->next;  // 前指针
        ListNode* bp = head;  // 后指针
        bp->next = nullptr;  // 需要将头节点的next指针先置null
        while(fp){
            ListNode* tp = fp->next; 
            fp->next = bp;
            bp = fp;
            fp = tp;
        }
        return bp;
    }