链表理论基础

链表是一种由指针串联在一起的线性结构，每一个节点都由一个数据域和一个指针域组成。

链表的类型有：单链表、双链表、循环链表。

链表的存储方式：在内存中不连续分布。

链表的定义很多人因为不重视而忽略，手写就显得很重要,如下所示：

// 单链表

struct ListNode {

    int val;  // 节点上存储的元素

    ListNode *next;  // 指向下一个节点的指针

    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数

};

203.移除链表元素

题目链接：203.移除链表元素

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

示例 1：

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

输出：[1,2,3,4,5]

思路

本题其实有两种代码解法，

一是：直接使用原来的链表来进行删除操作

二是：设置一个虚拟的头结点再进行删除操作

这里就不用第一种方案，因为第二种方便且实用。

代码如下（c++）：

class Solution {

public:

    ListNode* removeElements(ListNode* head, int val){

    	dummy head = new();、、设置一个虚拟头结点

    	dummy head->next = head;//让虚拟头节点指向了头节点

		cur = dummy head;

		//实际要删除的是cur->next,才能让cur指向删除后的元素

		while(cur->next != Null){

			if(cur->next->val == target){

				cur->next = cur->next->next;//完成删除操作

			else//没有找到要删除的目标值

				cur = cur->next;//继续往下遍历

			}

			return dummy head->next;//这里要返回的是虚拟头节点的下一个

			//即：新链表的头节点，原head可能已经删除

			//头节点的指针是不能改动的，遍历链表的时候要定义一个

			//临时的指针cur

		} 

	}

707.设计链表

题目链接：707.设计链表

题目描述：在链表类中实现这些功能：

获取链表第index个节点的数值   //get(index)

在链表的最前面插入一个节点   //addAtHead(val)

在链表的最后面插入一个节点   //addAtTail(val)

在链表第index个节点前面插入一个节点   //addAtIndex(index,val)

删除链表的第index个节点   //deleteAtIndex(index)

思路

可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目。

直接上代码：

class MyLinkedList {

public:

    // 定义链表节点结构体

    struct LinkedNode {

        int val;

        LinkedNode* next;

        LinkedNode(int val):val(val), next(nullptr){}

    };

	int get(int n) {

        if (n > (_size - 1) || n < 0) {

            return -1;

	    }//这里n就是第n个节点的n，若n<0||n>size - 1,则n不合法

  /*遍历链表的时候，要定义一个cur(临时)指针来遍历而不是直接操作头指针

因为操作完链表后，我们要返回头结点，如果上来就操作头节点那么他的值都改了，不得行*/

	cur = dummyhead->next;//让cur直接指向当前节点，即第零号节点（head节点）

	while(n){

		cur = cur->next;

		n--;

	}

	return cur->val;//想象直接特殊情况 第0个节点

}

	// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点

	void addAtHead(int val) {

        LinkedNode* newNode = new LinkedNode(val);//获取一个新节点

        newNode->next = _dummyHead->next;//正确的顺序是新节点的后继指向虚拟节点（头检点）的后继

        _dummyHead->next = newNode;//再让头节点的后继指向新节点

        _size++;

    }

    // 在链表尾部添加一个节点

    void addAtTail(int val) {

        LinkedNode* newNode = new LinkedNode(val);//tongshang

        LinkedNode* cur = _dummyHead;//

        while(cur->next != nullptr){// 当cur节点的后一个节点为空，循环终止

            cur = cur->next;

        }

        cur->next = newNode;//直接指向新节点，即加入

        _size++;

    }

    //在第n个节点前插入节点......

    /*第n个节点其实就是cur->next*/

	newNode = new LinkedNode(val);

        LinkedNode* cur = _dummyHead;

        while(n--) {

            cur = cur->next;

        }

        newNode->next = cur->next;

        cur->next = newNode;

        _size++;

    // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的

    void deleteAtIndex(int index) {

        if (index >= _size || index < 0) {

            return;

        }

        LinkedNode* cur = _dummyHead;

        while(n--) {

            cur = cur ->next;

        }

     cur->next = cur->next->next;

     size--;

206.反转链表

题目链接：206.反转链表

题目描述：题意：反转一个单链表。

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

主要思路

改变链表的next指针指向即可实现链表的反转。

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。

代码实现

双指针法：

Copy

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;

    }

};

总结

反转链表下次手撕一遍，链表这节有点基础，尽快拿下。

巴特西

代码随想录训练营day 4|链表基础理论，移除链表元素，设计链表，反转链表