链表面试题目

1,给定一单链表A1->A2->A3->......->AN, 转换为A2->A1->A4->A3->.....->AN(如果N是偶数），转换为 A1->A3->A2->A5->A4->....->AN(如果N是奇数），要求是只能便利一遍链表。

#include <stdio.h>
#include <stdlib.h>
 
typedef struct _Node Node;
 
struct _Node {
    int data;
    Node* next;
};
 
Node* node_new(int data, Node* next) {
    Node* node = (Node*)(malloc(sizeof(Node)));
    node->data=data;
    node->next=next;
    return node;
}
 
void node_free(Node* node) {
    free(node);
}
 
typedef int BOOL;
#define FALSE (0)
#define TRUE (!FALSE)
 
BOOL vswap_inner(Node** pp, Node** dangling) {
    // pp: input as the current head node
    //     output as the even point.
    // dangling: output only
    if(*pp==NULL) {
        return TRUE;
    } else {
        Node* first = *pp;
        Node* rest = first->next;
        Node* ndangling;
        BOOL even = vswap_inner(&rest,&ndangling);
        if(even) {
            *pp=rest;
            *dangling=first;
            return FALSE;
        } else {
            ndangling->next = first;
            first->next = rest;
            *pp=ndangling;
            //*dangling=NULL; // Not useful
            return TRUE;
        }
    }
}
 
void vswap(Node** pp_head) {
    Node *dangling = NULL;
    BOOL even = vswap_inner(pp_head,&dangling);
    if(!even) {
        dangling->next = *pp_head;
        *pp_head=dangling;
    }
}
 
void node_seq_print(Node* node) {
    if(node==NULL) {
        printf("\n");
    } else {
        printf("%d ",node->data);
        node_seq_print(node->next);
    }
}
 
int main() {
    Node *node = node_new(1,  
            node_new(2,  
                node_new(3,  
                    node_new(4,  
                        node_new(5, NULL)
                        ))));
 
    Node *node2 = node_new(1,  
            node_new(2,  
                node_new(3,  
                    node_new(4, NULL)
                        )));
 
    vswap(&node);
    vswap(&node2);
 
    node_seq_print(node);
    node_seq_print(node2);
 
    return 0;
} 

2,逆序一个链表

//定义数据结构
struct Node
{
    Node(int i):data(i),next(0){}
    int data;
    Node* next;
};

Node* reverseList(Node* head)
{
    if(head==NULL||head->next==NULL)
        return head;
    Node* p1=head;
    Node* p2=p1->next;
    Node* p3=p2->next;
    p1->next=NULL;
    while(p3!=NULL)
    {
        p2->next=p1;
        p1=p2;
        p2=p3;
        p3=p3->next;
    }
    p2->next=p1;
    head=p2;
    return head;
}

Node* recursiveReverseList(Node* head) //递归方法逆序
{
    Node *rHead;
    if ((head == NULL) || (head->next == NULL))
    {
        return head;
    }
    else
    {
        rHead = recursiveReverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return rHead;
    }
}

//释放带环的节点
void freeList(Node* head)
{
    Node* p;
    Node* tmp;
    for(p=head;p;p=tmp)
    {
        tmp=p->next;
        delete p;
    }
}

//打印链表中的数据,存在环,必定是死循环
void printList(Node* head)
{
    Node* p;
    for(p=head;p;p=p->next)
        cout<< p->data<<(p->next? " ":"");
    cout<<endl;
    return;
}


int main()
{
    Node *node=new Node(0);
    Node* head=node;
    for(int i=1;i<7;++i)
    {
        node->next=new Node(i);
        node=node->next;
    }
    printList(head);
    head=reverseList(head);
    printList(head);
    head=recursiveReverseList(head);
    printList(head);
    free(head);

    return 0;
}

3,合并两个有序链表

#include <iostream>
using namespace std;

//定义数据结构
struct Node
{
    Node(int i):data(i),next(0){}
    int data;
    Node* next;
};


//释放带环的节点
void freeList(Node* head)
{
    Node* p;
    Node* tmp;
    for(p=head;p;p=tmp)
    {
        tmp=p->next;
        delete p;
    }
}

//打印链表中的数据,存在环,必定是死循环
void printList(Node* head)
{
    Node* p;
    for(p=head;p;p=p->next)
        cout<< p->data<<(p->next? " ":"");
    cout<<endl;
    return;
}

//非递归合并两个有序链表
Node * Merge(Node *head1 , Node *head2)
{
    if ( head1 == NULL)
        return head2 ;
    if ( head2 == NULL)
        return head1 ;
    Node *head = NULL ;
    Node *p1 = NULL;
    Node *p2 = NULL;
    if ( head1->data < head2->data )
    {
        head = head1 ;
        p1 = head1->next;
        p2 = head2 ;
    }
    else
    {
        head = head2 ;
        p2 = head2->next ;
        p1 = head1 ;
    }
    Node *pcurrent = head ;
    while ( p1 != NULL && p2 != NULL)
    {
        if ( p1->data <= p2->data )
        {
            pcurrent->next = p1 ;
            pcurrent = pcurrent->next ;
            p1 = p1->next ;
        }
    else
    {
        pcurrent->next = p2 ;
        pcurrent = pcurrent->next ;
        p2 = p2->next ;
    }
    }
    if ( p1 != NULL )
        pcurrent->next = p1 ;
    if ( p2 != NULL )
        pcurrent->next = p2 ;
    return head ;
}

//递归合并两个有序链表
Node * ReMerge(Node *head1 , Node *head2)
{
    if ( head1 == NULL)
        return head2 ;
    if ( head2 == NULL)
        return head1 ;
    Node *head = NULL ;
    if ( head1->data < head2->data )
    {
        head = head1 ;
        head->next=ReMerge(head1->next,head2);
    }
    else
    {
        head = head2 ;
        head->next=ReMerge(head1,head2->next);
    }
    return head ;
}


int main()
{
    Node *node1=new Node(0);
    Node* head1=node1;
    for(int i=1;i<9;i+=3)
    {
        node1->next=new Node(i);
        node1=node1->next;
    }
    printList(head1);

    Node *node2=new Node(1);
    Node* head2=node2;
    for(int i=3;i<9;i+=2)
    {
        node2->next=new Node(i);
        node2=node2->next;
    }
    printList(head2);

    //Node* head=Merge(head1,head2);
    Node* head=ReMerge(head1,head2);
    printList(head);

    free(head);
    return 0;
}