考研生活day2--王道课后习题2.3.1、2.3.2、2.3.3

2.3.1

题目描述：

这题和曾经做过的LeetCode203.移除元素一模一样，所以我们就使用LeetCode进行书写，题目链接203. 移除链表元素 - 力扣（LeetCode）

解题思路

·大家的第一反应肯定是根据书上所学的书写方法一样书写，但是书上有一种情况没有说明，那就是如果要删除的节点是头节点该如何处理，这里我们就要考虑到头结点是如何处理的

·处理头节点可以直接对链表操作，也可以使用其他方法处理，在这里我提供一个方法，就是使用虚拟头结点对头结点操作，也就是在链表头结点前定义一个虚拟头结点，这样就可以把头结点当作普通节点进行处理了

·大家可能不明白我我说的意思，可以直接看代码，就可以理解了

代码如下：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0);//定义一个虚拟节点值为0
        dummyHead->next = head;//虚拟头结点指向链表头结点
        ListNode* cur = dummyHead;//定义临时节点用于遍历链表
        while(cur->next != NULL){
            if(cur->next->val == val){//书上的删除节点操作
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }else{
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;//删除虚拟头结点
        return head;
    }
};

2.3.2

题目描述

解题思路

1.我们在链表的操作中，一定要记下被操作元素的前驱结点，而后继节点可以很轻易的得到

2.这道题和上一题没有什么本质上的区别，我们只需要再定义一个minn变量，用于记录下当前最小节点的前驱即可

3.所以我们只需要不断的比较cur->next就可以了

4.再用一个临时节点temp用于记录cur->next即可

代码如下：

#include <iostream>
using namespace std;

typedef struct LNode
{
    int data;
    struct LNode* next;
} LNode, * LinkList;

// 头插法
void HeadInsert(LinkList& L)
{
    int val = 0;
    while (cin >> val)
    {
        LNode* s = new LNode;
        s->data = val;
        s->next = L->next;
        L->next = s;

        if (cin.get() == '\n')
        {
            break;
        }
    }
}

// 尾插法
void TailInsert(LinkList& L)
{
    int val = 0;
    LNode* r = L;
    while (cin >> val)
    {
        LNode* s = new LNode;
        s->data = val;
        r->next = s;
        r = s;
        r->next = NULL;

        if (cin.get() == '\n')
        {
            break;
        }
    }
}

// 遍历输出链表元素
void Print(LinkList L)
{
    LNode* p = L->next;
    while (p)
    {
        cout << p->data << '\t';
        p = p->next;
    }
    cout << endl;
}


void DelMinValue(LinkList& L) {
    LNode* p, * pre;
    p = L->next, pre = L;

    LNode* minp, * minpre;
    minp = p; minpre = pre;

    while (p) {
        if (p->data < minp->data) {
            minpre = pre;
            minp = p;
        }
        pre = p;
        p = p->next;
    }
    minpre->next = minp->next;
    delete minp;
}


int main()
{
    LinkList L = new LNode;
    TailInsert(L);

    DelMinValue(L);
    Print(L);
}

运行结果

2.3.3

这道题也与LeetCode206.反转链表一致，继续使用LeetCode进行学习206. 反转链表 - 力扣（LeetCode）

解题思路

1.可以重新定义一个链表，将第一个链表中的元素取出后，再放入新建的链表中，即可实现，这个方法同样也可以借助栈进行求解

2.可以考虑使用双指针法，不理解双指针法的同学可以不考虑使用这个方法

代码如下

双指针法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp;//保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur){
            temp = cur->next;// 保存一下，cur的下一个节点，因为要改变cur->next
            cur->next = pre;//进行翻转操作
            //更新pre和cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};