单链表反转

悠悠 2022-03-09 11:26 363阅读 0赞

单链表的翻转是一道很基本的算法题。

方法1：将单链表储存为数组，然后按照数组的索引逆序进行反转。

方法2：使用三个指针遍历单链表，逐个链接点进行反转。

方法3：从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。

方法1的问题是浪费空间。方法2和方法3效率相当。一般方法2较为常用。

方法2代码：

Node * ReverseList(Node *head)
    {
    	Node *p1,*p2,*p3;
    	if(head==NULL||*head==NULL)
    	return head;
    	p1=head;
    	p2=p1->next;
    	while(p2)             //注意条件
    	{
    		p3=p2->next;	      //要改变p2->next的指针，所以必须先保留p2->next	     
    		p2->next=p1;
    		p1=p2;		      //循环往后
    		p2=p3;
    	}
    	head->next=NULL;   //原先的head已经变成tail，别忘了置空，只有到这步才能置空
    	*head=p1;
    	return head;
    }

方法3代码：

Node* ReverseList(Node* head) 
    { 
        Node *p,*q;  
        p=head->next; 
        while(p->next!=NULL)      //在这个循环过程中p所指的元素一直是不变的
    	{
            q=p->next; 
            p->next=q->next; 
            q->next=head->next; 
            head->next=q; 
    	} 
        p->next=head;            //相当于成环 
        head=p->next->next;       //新head变为原head的next 
        p->next->next=NULL;     //断掉环 
        return head;   
    }

附加一道题目，《编程之美》的3.4：从无头链表中删除节点。假设有一个没有头指针的单链表。一个指针指向此链表中间的一个节点（不是第一个，也不是最后一个节点），请将该节点从单链表中删除。

分析：无法知道前续的节点，只能知晓后续节点，所以存在一个难点，如何将前后两段连接起来。由于链表是要删除操作，所以多处一个可用空间。所以可以用翻转操作方法1的思想来解决。将需要删除节点的节点复制为其后续节点就可以了，这样后续节点已经不再链表中，可以进行析构。