单链表两两反转

小咪咪 2022-10-27 05:27 87阅读 0赞

# 单链表两两反转 #

将： 1 2 3 4 5  
反转成：2 1 4 3 5

#include <iostream>
    #include<stack>
    #include<assert.h>
    using namespace std;
    
    typedef struct node
    { 
        int data;
        node *next;
    }node;
    
    /*增加*/
    node * add(int n, node * head) 
    { 
    	node * t = new node;
    	t->data = n;
    	t->next = NULL;
    	if (head == NULL) 
    	{ 
    		head = t;
    	}
    	else if (head->next == NULL) 
    	{ 
    		head->next = t;
    	}
    	else 
    	{ 
    		node * p = head->next;
    		while (p->next != NULL) 
    		{ 
    			p = p->next;
    		}
    		p->next = t;
    	}
    	return head;
    }
    /*输出链表数值*/
    void print(node * head) 
    { 
    	node * p = head;
    	while (p != NULL) 
    	{ 
    		cout << p->data << " ";
    		p = p->next;
    	}
    	cout << endl;
    }
    node *reverse(node *head)
    { 
        if(head==NULL||head->next==NULL)
        { 
            return head;
        }
        node *p1=head;/*当前节点*/
        node *p2=head->next;/*下个节点*/
        node *temp;/*下个节点*/   
        node *previous=NULL;/* */
        node * newHead = p2 == NULL ? p1 : p2;
    
        while(p2!=NULL)
        { 
            temp=p2->next;
            p2->next=p1;
            p1->next=temp;
            if(previous!=NULL)
            { 
                previous->next=p2;
            }
            if(temp==NULL)
            { 
                break;
            }
            previous=p1;
            p1=temp;
            p2=temp->next;
        }
        return newHead;
    }
        
    
    int main() 
    { 
        node *head=NULL;
        for(int i=1;i<10;i++)
        { 
            head=add(i,head);
        }
        print(head);
        head=reverse(head);
        print(head);
    
        cout << "Hello World!" << endl;
    }

![在这里插入图片描述][20210203190200371.png]

[20210203190200371.png]: /images/20221024/7a9a65a4f37c40668d659eab511cf359.png