单链表

 1 #include<iostream>
 2 using namespace std;
 3  
 4 //单链表结构体
 5 typedef struct student
 6 {
 7     int data;
 8     struct student *next;
 9 }node;
10  
11 //建立单链表
12 node *create()
13 {
14     node *head,*p,*s;
15     int x,cycle=1;
16     head=(node*)malloc(sizeof(node)); //建立头节点
17     p=head;
18     while(cycle)
19     {
20         printf("
Please input the data:");
21         scanf("%d",&x);
22         if(x!=0)
23         {
24             s=(node*)malloc(sizeof(node));//每次新建一个节点
25             s->data=x;
26             printf("
%d",s->data);
27             p->next=s;
28             p=s;
29         }
30         else
31         {
32             cycle=0;
33         }
34     }
35     head=head->next;
36     p->next=NULL;
37     printf("
   yyy   %d",head->data);
38     return (head);
39 }
40  
41 //单链表测长
42 int length(node *head)
43 {
44     int n=0;
45     node *p;
46     p=head;
47     while(p!=NULL)
48     {
49         p=p->next;
50         n++;
51     }
52     return (n);
53 }
54  
55 //单链表打印
56 void print(node *head)
57 {
58     node *p;
59     int n;
60     n=length(head);
61     printf("
Now,These %d records are :
",n);
62     p=head;
63     if(head!=NULL)
64         p=p->next;
65     while(p!=NULL)
66     {
67         printf("
   uuu  %d    ",p->data);
68         p=p->next;
69     }
70 }

//单链表删除节点
node *remove(node *head ,int num)
{
    node *p1,*p2;
    p1=head;
    while(num!=p1->data && p1->next!=NULL)//查找data为num的节点
    {
        p2=p1;
        p1=p1->next;
    }
    if(num==p1->data) //如果存在num节点，则删除
    {
        if(p1==head)
        {
            head=p1->next;
            free(p1);
        }
        else
        {
            p2->next=p1->next;
        }
    }
    else
    {
        printf("
%d could not been found",num);
    }
    return (head);
}

//单链表插入节点
node *insert(node *head,int num)
{
    node *p0,*p1,*p2;
    p1=head;
    p0=(node *)malloc(sizeof(node));
    p0->data=num;
    while(p0->data > p1->data && p1->next!=NULL)
    {
        p2==p1;
        p1=p1->next;
    }
    if(p0->data<=p1->data)
    {
        if(head==p1)
        {
            p0->next=p1;
            head=p0;
        }
        else
        {
            p2->next=p0;
            p0->next=p1;
        }
    }
    else
    {
        p1->next=p0;
        p0->next=NULL;
    }
    return (head);
}

//单链表排序
node *sort(node *head)
{
    node *p,*p2,*p3;
    int n;
    int temp;
    n=length(head);
    if(head==NULL ||head->next==NULL)//如果只有一个或者没有节点
        return head;
    p=head;
    for(int j=1;j<n;++j)
    {
        p=head;
        for(int i=0;i<n-j;++i)
        {
            if(p->data > p->next->data)
            {
                temp=p->data;
                p->data=p->next->data;
                p->next->data=temp;
            }
            p=p->next;
        }
    }
    return (head);
}

//单链表逆置
node *reverse(node *head)
{
    node *p1,*p2,*p3;
    if(head==NULL || head->next==NULL)
        return head;
    p1=head;
    p2=p1->next;
    while(p2)
    {
        p3=p2->next;
        p2->next=p1;
        p1=p2;
        p2=p3;
    }
    head->next=NULL;
    head=p1;
    return head;
}

//删除单链表的头元素
void RemoveHead(node *head)
{
    node *p;
    p=head;
    head=head->next;
    free(p);
}

//给出一个单链表，不知道节点N的值，怎么只遍历一次就可以求出中间节点
void searchmid(node *head,node *mid)
{
    node *p,*q;
    p=head;
    q=head;
    while(p->next->next!=NULL)
    {
        p=p->next->next;
        q=q->next;
        mid=q;
    }
}

给定一个单向链表，设计一个时间优化并且空间优化的算法，找出该链表的倒数第m个元素。实现您的算法，注意处理相关的出错情况。m定义为当m=0时，返回链表最后一个元素。

解析：这是一个难题，我们需要的是倒数第m个元素，所以如果我们从某个元素开始，遍历了m个元素之后刚好到达链表末尾，那么这个元素就是要找的元素。也许从链表的尾部倒推回去不是最好的办法，那么我们可以从链表头开始计数。

思路一：我们可以先一次遍历求出链表的总长度n，然后顺序变量求出第n-m个元素，那么这个就是我们要找的元素了。

思路二：我们用两个指针，一个当前位置指针p和一个指向第m个元素的指针q，需要确保两个指针之间相差m个元素，然后以同样的速度移动它们，如果当q到达链表末尾时，那么p指针就是指向倒数第m个元素了。

答案：

//思路一
node *searchLastElement1(node *head,int m)
{
    if(head==NULL)
        return NULL;
    node *p=head;
    int count=0;
    while(p!=NULL)
    {
        p=p->next;
        count++;
    }
 
    if(count<m)
        return NULL;
 
    p=head;
    for(int i=0;i<count-m;i++)
    {
        p=p->next;
    }
    return p;
}
 
//思路二
node *searchLastElement2(node *head,int m)
{
    if(head==NULL)
        return NULL;
    node *p,*q;
    p=head;
    for(int i=0;i<m;i++)
    {
        if(p->next!=NULL)
        {
            p=p->next;
        }
        else
        {
            return NULL;
        }
    }
 
    q=head;
    while(p->next!=NULL)
    {
        p=p->next;
        q->next;
    }
    return q;
}

已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。(保留所有结点，即便大小相同）

 1 Node * Merge(Node *head1 , Node *head2)
 2 {
 3     if ( head1 == NULL)
 4         return head2 ;
 5     if ( head2 == NULL)
 6         return head1 ;
 7     Node *head = NULL ;
 8     Node *p1 = NULL;
 9     Node *p2 = NULL;
10     if ( head1->data < head2->data )
11     {
12         head = head1 ;
13         p1 = head1->next;
14         p2 = head2 ;
15     }
16     else
17     {
18         head = head2 ;
19         p2 = head2->next ;
20         p1 = head1 ;
21     }
22     Node *pcurrent = head ;
23     while ( p1 != NULL && p2 != NULL)
24     {
25         if ( p1->data <= p2->data )
26         {
27             pcurrent->next = p1 ;
28             pcurrent = p1 ;
29             p1 = p1->next ;
30         }
31         else
32         {
33             pcurrent->next = p2 ;
34             pcurrent = p2 ;
35             p2 = p2->next ;
36         }
37     }
38     if ( p1 != NULL )
39         pcurrent->next = p1 ;
40     if ( p2 != NULL )
41         pcurrent->next = p2 ;
42     return head ;
43 }

已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序，这次要求用递归方法进行。

 1 Node * MergeRecursive(Node *head1 , Node *head2)
 2 {
 3     if ( head1 == NULL )
 4         return head2 ;
 5     if ( head2 == NULL)
 6         return head1 ;
 7     Node *head = NULL ;
 8     if ( head1->data < head2->data )
 9     {
10         head = head1 ;
11         head->next = MergeRecursive(head1->next,head2);
12     }
13     else
14     {
15         head = head2 ;
16         head->next = MergeRecursive(head1,head2->next);
17     }
18     return head ;
19 }

如何判断一个单链表是有环的？（注意不能用标志位，最多只能用两个额外指针）

 1 struct node { char val; node* next;}
 2    bool check(const node* head) {} //return false : 无环；true: 有环一种O（n）的办法就是（搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然）：
 3 bool check(const node* head)
 4 {
 5     if(head==NULL)  returnfalse;
 6     node *low=head, *fast=head->next;
 7     while(fast!=NULL && fast->next!=NULL)
 8     {
 9         low=low->next;
10         fast=fast->next->next;
11         if(low==fast) returntrue;
12     }
13     return false;
14 }

双链表

  1 //待验证，待完善
  2 #include "stdafx.h"
  3 #include <stdio.h>
  4 #include <iostream>
  5 using namespace std;
  6 typedef struct NODE
  7 {
  8     int data;
  9     struct NODE *pre;
 10     struct NODE *next;
 11 }node;
 12 
 13 node *create()
 14 {
 15     node *head, *tmp, *pnode;
 16     int x,cycle = 1;
 17     head = (node*)malloc(sizeof(node));
 18     tmp = head;
 19     while (cycle)
 20     {
 21         scanf("%d",&x);
 22         if (x != 0)
 23         {
 24             pnode = (node*)malloc(sizeof(node));
 25             pnode->data = x;
 26             tmp->next = pnode;
 27             pnode->pre = tmp;
 28             tmp = pnode;
 29         }
 30         else
 31             cycle = 0;
 32     }
 33     head = head->next;
 34     tmp->next = NULL;
 35     head->pre = NULL;
 36     printf("%d
",head->data);
 37     return head;
 38 }
 39 
 40 node *del(node*head, int num)
 41 {
 42     node *tmp;
 43     tmp = head;
 44     while (num != tmp->data && tmp->next != NULL)
 45     {
 46         tmp = tmp->next;
 47     }
 48     if (num == tmp->data)
 49     {
 50         if (tmp == head)
 51         {
 52             head = tmp->next;
 53             head->pre = NULL;
 54             free(tmp);
 55         }
 56         else if (tmp->next == NULL)
 57         {
 58             tmp->pre->next = NULL;
 59         }
 60         else
 61         {
 62             tmp->pre->next = tmp->next;
 63             tmp->next->pre = tmp->pre;
 64         }
 65         return head;
 66     }
 67 }
 68 
 69 node* insert(node*head, int num)
 70 {
 71     node *p0, *p1;
 72     p1 = head;
 73     p0 = (node*)malloc(sizeof(node));
 74     p0->data = num;
 75     while (p0->data > p1->data && p1->next != NULL)
 76     {
 77         p1 = p1->next;
 78     }
 79     if (p0->data <= p1->data)
 80     {
 81         if (head == p1)
 82         {
 83             p0->next = p1;
 84             p1->pre = p0;
 85             head = p0;
 86         }
 87         else if (p1->next != NULL)
 88         {
 89             p1->next = p0;
 90             p0->pre = p1;
 91             p0->next = NULL;
 92         }
 93         else
 94         {
 95             p1->pre->next = p0;
 96             p0->next = p1;
 97             p0->pre = p1->pre;
 98             p1->next = p0;
 99         }
100     }
101     return head;
102 }
103 
104 int _tmain(int argc, _TCHAR* argv[])
105 {
106     create();
107     return 0;
108 }