边教边学系列---链表的常见 *** 作及代码_C

#边教边学系列—链表的常见 *** 作及代码

1.定义一个结点模板

template<typename T>
struct Node {
	T data;
	Node *next;
	Node() : next(nullptr) {}
	Node(const T &d) : data(d), next(nullptr) {}
};

2.删除 p 结点后面的元素

template<typename T>
void Remove(Node<T> *p) {
	if (p == nullptr || p->next == nullptr) {
		return;
	}
	auto tmp = p->next->next;
	delete p->next;
	p->next = tmp;
}

3.在 p 结点后面插入元素

template<typename T>
void Insert(Node<T> *p, const T &data) {
	auto tmp = new Node<T>(data);
	tmp->next = p->next;
	p->next = tmp;
}

4.遍历链表

template<typename T, typename V>
void Walk(Node<T> *p, const V &vistor) {
	while(p != nullptr) {
		vistor(p);
		p = p->next;
	}
};

5.查找倒数第K个元素

class solution{
public:
	ListNode* getKthFromEnd(LinkNode* head , int k){
		ListNode *p = head, *q = head;  //初始化
		while(k--){				//先让q移动K个位置
			q = q ->next;
		}
		while(q != nullptr){    //同时移动，直到q为空
			q = q ->next;
			p = p ->next;
		}
		return p;
	}
};

6.获取中间位置的元素

class Solution{
public:
	ListNode* getMidFrom(ListNode* head){
		ListNode *p = head, *q = head;  //初始化
		while(q != nullptr && q -> next != nullptr){   //元素个数为偶数或奇数的情况
			p = p->next;
			q = q->next->next;
		}
		return p;
	}
};

7.是否存在环的问题

class Solution {
public:
    bool hasCycle(ListNode *head) {		//双指针一起移动，如果有环，快的一定会和慢的相遇！！
        ListNode *slow = head;		
        ListNode *fast = head;
        while(fast != nullptr) {		//
            fast = fast->next;
            if(fast != nullptr) {
                fast = fast->next;
            }
            if(fast == slow) {
                return true;
            }
            slow = slow->next;
        }
        return false;
    }
};

8.环的长度问题

class solution{
public:
	ListNode *slow = head;
	ListNode *fast = head;
	int i = 0;
	while(fast != nullptr) {
		fast = fast ->next;
		if (fast != nullptr) {
			fast = fast ->next;
		}
		if (fast == slow) {
			return i * 2;		//等于两次相遇的长度
		}
		slow = slow ->next;
		i++;
	}
};