数据结构_单链表题-2.1

一. 反转单链表

将一个单链表反过来。

个人思路（一团浆糊大错特错）

反转嘛，变最后为起点，依次反转过来就行了。
1）找到最后三个链表结点，分别保存下来，以最后一个为首地址。
2）最后一个链表结点指向倒数第二个链表（倒数第三个的next赋值给最后一个的next）
3）这样每隔一个链表结点依次反转。

问题

1）你要先遍历一遍才能找到最后一个链表
2）单链表，你怎么可能回溯找上流的链表

参考思路：三指针迭代（头部插入一个新的空链表）

1）首链表(n2)前创建一个NULL链表（n1)
2）把首链表指向的第二个链表地址保存下来(n3)
3）首链表指向n1,完成反转(n2->next=n1)
4）依次右移，像三个为一组的窗口去调整反转。

增益点：指针迭代

单链表是自上而下的单方向，思考方向应该还为从上而下。

代码

SListNode* reverseList(SListNode* head) {
	if (head == NULL || head->next == NULL)
		return head;
	SListNode* n1 = NULL;
	SListNode* n2 = head;
	SListNode* n3 = head->next;
	while (n2 != NULL)
	{
		n2->next = n1;
		
		n1 = n2;
		n2 = n3;
		if(n3!=NULL)
		n3 = n3->next;

	};

	return n1;
}

二. 单链表，有数量关系的处理

例如：
取单链表中间点
删链表倒数第几个数
…………

个人思路

1）遍历求长度
2）要第几个根据长度来看

问题

1）你要先遍历一遍才能找到最后一个链表，求长度
2）那这和数组有什么区别？效率不高
3）链表的长度本该没有什么意义。

参考思路：快慢指针

1）根据数量关系，中间点就是快指针到末尾时，慢指针以一半的速度到达中间位置。
倒数第n个，当快指针到末尾时，慢指针以落后n的速度到达相应的位置。

增益点：快慢指针，边遍历边根据数量关系定位

在快指针遍历完整个数组时，把之后的第二遍遍历用慢指针代替。适合有数量关系的题。

代码

一半的速度找到中间点。

while(cur->next)
    {
        cur=cur->next;
        if(cur->next)
        cur=cur->next;

        low=low->next;
    }