算法-链表

发表于 | 分类于 | | 阅读次数

从尾到头输出链表

题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。

从头到尾遍历链表，每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始输出结点的值，此时输出的结点的顺序已经反转过来了。该方法需要维护一个额外的栈，实现起来比较麻烦。
既然想到了栈来实现这个函数，而递归本质上就是一个栈结构。于是很自然的又想到了用递归来实现。要实现反过来输出链表，我们每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
void PrintListReversely(ListNode* pListHead)
{
      if(pListHead != NULL)
      {
            // Print the next node first
            if (pListHead->m_pNext != NULL)
            {
                  PrintListReversely(pListHead->m_pNext);
            }
            // Print this node
            printf("%d", pListHead->m_nKey);
      }
}

寻找链表的第n个节点

单链表差集

已知集合A和B的元素分别用不含头结点的单链表存储，函数difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。
例如，若集合A={5,10,20,15,25,30}，集合B={5,15,35,25}，完成计算后A={10,20,30}。
链表结点的结构类型定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct node
{
    int elem;
    node* next;
};
void difference(node** LA , node* LB)
{
    node *pa , *pb , *pre , *q;
    pre = NULL;
    pa = *LA; //1
    while(pa)
    {
        pb = LB;
        while( pb && ( pa->elem != pb->elem ) )            //2
            pb = pb->next;
        if( pb )                           //3
        {
            if( !pre )
                *LA = pa->next ;        //4
            else
                pre = pa->next;         //5
            q = pa;
            pa = pa->next;
            free(q);
        }
        else
        {
            pre = pa;                 //6
            pa = pa->next;
        }
    }
}