数据结构-单链表的多指针问题

数据结构-单链表的多指针问题

问题1：实现对单链表的逆序

思路：单链表想要逆序，本质上是改变链表中各个节点间的相互关系，而决定各个节点间相互关系的也只有不同节点间的指针，指针决定了节点的先后顺序。因此，想要实现对单链表的逆序，关键是将链表中的指针翻转过来，让从A-->B的变成从B-->A的。

整个过程的思路如下：

 代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include
typedef  int SLTDateType;
struct ListNode
{
	SLTDateType data;
	struct ListNode* next;
};//首先初始化节点的结构体类型并宏定义变量类型    
struct ListNode* reverseList(struct ListNode* head)
{
	if (head == NULL)
		return NULL;//如果头指针为空的话，说明整个链表为空，也就没有研究的必要了
	struct ListNode* n1, * n2, * n3;//创建三个节点类型的指针n1,n2,n3
	n1 = NULL;
	n2 = head;
	n3 = head->next;
	while (n2)//当n2不为空指针时，循环一直继续
	{
		n2->next = n1;//将n2所指向节点的指针赋为空指针
		n1 = n2;//把n2的地址赋给n1，亦即让n1指向原先n2指向的节点
		n2 = n3;//让n2指向原先n3指向的节点
		if (n3)//如果n3不为空，则n3向后移动一位
			n3 = n3->next;
	}
	return n1;
}

问题1的另一种实现方法：头插法（实现方式不同，但核心思想一致，都是改变指针的方向。cur-->next=newhead,newhead再向后移，newhead=cur,还要有一个指针next保存指针的地址，避免因为指针cur的变化让指针丢失）

 

#define _CRT_SECURE_NO_WARNINGS
#include
typedef  int SLTDateType;
struct ListNode
{
	SLTDateType data;
	struct ListNode* next;
};//首先初始化节点的结构体类型并宏定义变量类型    
struct ListNode* reverseList(struct ListNode* head)
{
	struct ListNode* cur = head;//将头指针赋给结构体型指针cur
	struct ListNode* newhead = NULL;//创建一个结构体型空指针newhead
	while (cur)//当指针cur不为空时，整个while循环会一直继续
	{
		struct ListNode* next = cur->next;//向后移动的同时为指针cur留下了一份拷贝，接下来就可以对指针cur随意进行变化了
		cur->next = newhead;//本方法的核心思想，即反转指针
		newhead = cur;
		cur = next;//下面的这两步都是按部就班的向后移动指针
	}
	return newhead;//在全部处理完之后，newhead变成了单链表的头节点，返回newhead即可
}

问题2：中间节点问题，对于有奇数个节点的单链表，找出期中间那个节点，对于有偶数个节点的链表，找出其中间两个节点的后一个。

思路：这类问题要利用快慢指针的思想，一个指针走的较快，另一个较慢，当快指针的速度是慢指针的二倍时，快指针走到链表末端时，慢指针正好走到中间节点处。

#define _CRT_SECURE_NO_WARNINGS
#include
typedef  int SLTDateType;
struct ListNode
{
	SLTDateType data;
	struct ListNode* next;
};//首先初始化节点的结构体类型并宏定义变量类型    
struct ListNode* reverseList(struct ListNode* head)
{
	struct ListNode* slow, * fast;//定义两个结构体类型指针
	slow = fast = head;//将头指针的赋给两个指针
	while (fast && fast->next)//括号内的判断条件是，只有指针fast和指针fast->next都不为空时，while循环才会继续下去，只要有一个为空，就说明
		//奇数个的单链表或者偶数个的单链表已经走完了
	{
		slow = slow->next;
		fast = fast->next->next;//指针slow一个循环向后走有一位，指针fast一个循环向后走两位
	}
	return slow;//程序运行完时，指针slow指向的节点就是我想要找的中间节点
}

问题3：寻找链表中的倒数第k个节点。

思路：仍然是双指针的思路，先让一个指针向后移动k位，然后再让另一个节点和已经移动k位的节点同时移动，两指针速度相同，当已经移动k位的指针向后移动到链表末端时，后移动的指针恰好指向链表的倒数第k个元素。

 

#define _CRT_SECURE_NO_WARNINGS
#include
typedef  int SLTDateType;
struct ListNode
{
	SLTDateType data;
	struct ListNode* next;
};//首先初始化节点的结构体类型并宏定义变量类型    
struct ListNode* reverseList(struct ListNode* head)
{
	struct ListNode* first, * after;
	first = after = head;
	int i = 0;
	int k = 0;
	for (i = 0; i < k; i++)
	{
		if (first == NULL)
		{
			return NULL;
		}
		first = first->next;
	}
	while (first != NULL)
	{
		first = first->next;
		after = after->next;
	}
	return after;
}

问题4：合并两个有序链表

#define _CRT_SECURE_NO_WARNINGS
#include
typedef  int SLTDateType;
struct ListNode
{
	SLTDateType data;
	struct ListNode* next;
};//首先初始化节点的结构体类型并宏定义变量类型    
struct ListNode* reverseList(struct ListNode* l1, struct ListNode* l2)//list node列表节点
{
	if (l1 == NULL)
		return l2;
	if (l2 == NULL)
		return l1;//以上这两个if都代表如果其中一个单链表为空的话，则返回另一个链表的指针（也就相当于返回整个链表）
	struct ListNode* head = NULL, * tail = NULL;//创建两个空指针
	while (l1 && l2)//只有当两个指针都不为空时，while循环才会继续
	{
		if (l1->data < l2->data)//如果指针l1指向节点的数据小于l2指向节点的数据
		{
			if (head == NULL)//如果指针为空，即我想要创建的新链表内还没有插入任何元素
			{
				head = tail = l1;//将两指针都指向插入的第一个节点
			}
			else//如果最终的链表内已经有节点了，则
			{
				tail->next = l1;//哪一个单链表上的节点的值小，尾节点就向哪一个链表延申伸
				tail = l1;//这里有一个思维上的省略过程，两步合起来看即tail=tail->next
			}
			l1 = l1->next;
		}
		else
		{
			if (head == NULL)//head指针的作用金局限于标记我要得出的单链表的头节点
			{
				head = tail = l2;
			}
			else
			{
				tail->next = l2;
				tail = l2;//tail->next=l2即相当于把指针l2指向的节点变成最后排序得到的单链表的尾节点，而且当单链表变长时，
				//尾节点也要实时更新，向后挪
			}
			l2 = l2->next;
		}
	}
	if (l1)
	{
		tail->next = l1;
	}
	if (l2)
	{
		tail->next = l2;
	}//当其中一个单链表全部比较完之后，另外一个也没有继续比较的意义了，直接插在最后得出的链表之后
	return head;
}