【数据结构】链表的基本操作

提示：主要是针对408数据结构线性表来学习总结 语言:C++

• 线性表
• 一、线性表基础
• 二、遍历单链表
• 三、头插法建立单链表
• • 迭代
  • 递归
• 四、尾插法建立单链表
• 五、单链表插入结点
• 六、单链表删除结点
• 附

简而言之：线性表是一种逻辑结构，表示元素之间一对一的相邻关系，一般讨论的是顺序存储结构（顺序表）和链式存储结构（链表）
我们主要谈论总结是链表的基础算法，大多数问题都是这些在这些基本算法上进而实现的。

这里的遍历是经典的快慢指针找链表的中间结点。
用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。

class Solution{
public:
	ListNode* middleNode(ListNode* head)
	{
		ListNode* slow = head;
		ListNode* fast = head;
		while(fast!=nullptr && fast->next=nullptr )
		{
			slow = slow->next;
			fast = fast->next->next;
		}
		return slow;
	}
};

头插法经常用于反转链表，虽然C++可以直接使用reverse,但是做题中一般是不允许的。

vector v = {5,4,3,2,1};
reverse(v.begin(),v.end());//v的值为1,2,3,4,5

核心：将当前节点的 next 指针改为指向前一个节点。
动画演示

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

//TODO

//核心代码
p=GetElem(L,i-1);
s->next=p->next;
p->next=s; 

//核心代码
p=GetElem(L,i-1);
q=p->next
p->next=q->next

参考自：
王道数据结构
代码参考自LeetCode