博客

目录

用对撞指针反转一个数组

快慢指针：

1.寻找链表中间节点

2.删除链表倒数第k个节点

用对撞指针反转一个数组

例：

输入：5 1 2 3 4 5

输出：5 4 3 2 1

#include <iostream>
using namespace std;

int main()
{
	int n = 0;
	int a[100];
	cin >> n;
	for (int i = 0;i < n;i++)
	{
		cin >> a[i];
	}
	int* left, * right;
	left = a;                 //左指针
	right = &(a[n - 1]);       //右指针   
	while (left <= right)
	{
		int tmp = 0;         //用指针交换两个数的值
		tmp = *left;
		*left = *right;
		*right = tmp;
		left++;              //交换完之后左指针向中间移动一位
		right--;             //右指针向右移动一位

	}
	for (int i = 0;i < n;i++)
		cout << a[i] << " ";

	return 0;
}

若要将数组逆序输出，最简单的一种方法是将数组逆序遍历一遍输出，但此种方法没有改变数组的实际顺序，只是将数组逆序输出了而已，实际意义不是很大。

所以我们采用双指针法：对撞指针

顾名思义，两个指针分别从数组的两端遍历，交换两个数的位置，“对撞”时即完成任务

Ps:双指针法也不一定要求left和right都是指针，也可以用left和right保存数组下标

如下，left、right分别保存数组的下标

int left,  right;
	left = 0;                 //左指针
	right = n - 1;       //右指针   
	while (left <= right)
	{
		int tmp = a[left];         //用指针交换两个数的值
		a[left] = a[right];
		a[right] = tmp;
		left++;              //交换完之后左指针向中间移动一位
		right--;             //右指针向右移动一位

	}

快慢指针：

1.寻找链表中间节点

给定一个头结点为

head

的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

https://leetcode-cn.com/problems/middle-of-the-linked-list/https://leetcode-cn.com/problems/middle-of-the-linked-list/



https://leetcode-cn.com/problems/middle-of-the-linked-list/

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode*fast,*slow;
        fast=head;
        slow=head;
        while(fast->next!=NULL&&fast->next->next!=NULL)
        {
            fast=fast->next->next;//快指针一次移动两步
            slow=slow->next;//慢指针一次移动一步
        }
        if(fast->next!=NULL&&fast->next->next==NULL)
        {
            slow=slow->next;//若有两个中间节点，返回第二个
        }
        return slow;
    }
};

2.删除链表倒数第k个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

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

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

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/



https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode*fast=head,*slow=head;
        if(head==NULL&&head->next==NULL)return NULL;
        for(int i=0;i<n;i++)//让快指针先走n步
        fast=fast->next;

        if(fast==NULL)
            return head->next;
        
        while(fast->next!=NULL)//然后快慢指针一起走，快指针到达链表尾时结束
        {
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return head;
    }
};

若要找到单链表的倒数第k个节点，一开始的思路是先把单链表遍历一遍，计数有多少个节点，随后再将单链表遍历一遍，找出倒数第k个节点。

若用快慢指针法，快指针先走n步，然后快慢一起走，直到快指针走到最后，要注意的是可能是要删除第一个节点，这个时候可以直接返回

head -> next