1，单链表反转

朱雀 2022-05-26 07:43 120阅读 0赞

题目：

顾名思义，就是反转一个单链表。

思路1：

重新开辟内存，简历一个新链表，然后从后面往前面复制。

由于单链表无法很容易得到当前节点前面的节点，所以，复制每一个节点都得从前往后找到该节点，

单个节点复制的时间复杂度为O(n)，整个复杂度则为O（n^2)，空间复杂度为O（n）。不可取。

思路2：

不开辟新内存，采用交换节点内容的方式。

前后两个指针，相互交换内容，之后前面的指针后移，后面的指针前移，再交换。

问题是后面指针前移的时间复杂度依然是O（n），所以时间复制度不变，仍为O（n^2）。不可取。

思路3,：

改变指针指向。时间复杂度为O（n），空间复杂度为O(1）。

注意：

输入可能为：

1，NULL

2，空链表，即只含有表头结点

3，单一结点，只有一个有效结点

4，多个结点

前三种情况都不需要处理。

反转当前结点pNode时，需要记录下一个结点pNext，且需要当前结点的上一个结点preNode。

第一个结点的反转比较特殊，初始化这些指针即可，且将第一结点的next置NULL。

结束之后，所有结点处理完了。加上表头结点即可。

注意：

有表头结点。

// LinkTable.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    #include <string>
    using namespace std;
    
    //链表的结构体
    struct node
    {
    	char val;
    	node * next;
    };
    
    //1.单链表反转
    struct node * create( string & str_link )
    {
    	int len = str_link.length();
    
    	struct node * phead = new node();     //带有表头的链表，表头中不存储任何元素
    	struct node * preNode = phead;
    	for( int i=0; i<len; i++ )
    	{
    		struct node * pNode = new node();
    		pNode->val = str_link[i];
    		pNode->next = NULL;
    		preNode->next = pNode;
    		preNode = pNode;
    	}
    	return phead;
    }
    
    void out_link( struct node * phead )
    {
    	if( phead == NULL )
    		return;
    	struct node * pNode = phead->next;
    	while( pNode )
    	{
    		cout <<pNode->val;
    		pNode = pNode->next;
    	}
    	cout << endl;
    }
    
    void reverse_link( struct node * phead )
    {
    	if( !phead || !phead->next || !phead->next->next ) //无链表，空链表，当个节点链表则返回
    		return;
    
    	//处理第一个节点
    	struct node * preNode = phead->next;
    	struct node * pNode = preNode->next;
    	preNode->next = NULL;
    
    	//从第二个节点开始处理
    	while(pNode)
    	{
    		struct node * pNext = pNode->next;
    		pNode->next = preNode;
    		preNode = pNode;
    		pNode = pNext;
    	}
    
    	//加上表头节点
    	phead->next = preNode;
    }
    
    void reverse_test()
    {
    	string str;
    	cin >> str;
    	struct node *phead = create( str );
    	out_link( phead );
    	reverse_link( phead );
    	out_link( phead );
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	reverse_test();
    	return 0;
    }