题目:快速找到未知长度单链表的中间结点

既然是面试题,就存在这普通方法和高级方法。

普通方法

  • 首先遍历一遍单链表,确定单链表的长度 L
  • 再从头结点出发循环 L/2 次找到单链表的中间结点
  • 该算法复杂度为:O(L+L/2) = O(3L/2)

得到表长

/* 遍历单链表得到表长 */
int GetLinkListLength(LinkList L)
{
    LinkList p;
    p = L->Next;
    int i = 0;

    while(p)
    {
        p = p->Next;
        i++;
    }
    printf("\n链表长度为:%d", i);
    return i;
}

找到中间结点

/* 获取中间结点 */
Status GetCenterElem(LinkList L, int i, ElemType *e)
{
    LinkList p;
    p = L->Next;
    for(int j = 0; j < i/2; j++)
    {
        p = p->Next;
    }
    *e = p->data;
    return OK;
}

完整代码

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;
typedef int Status;
typedef struct Node
{
    ElemType data;
    struct Node *Next;
} Node;
typedef struct Node *LinkList;

/* 遍历单链表得到表长 */
int GetLinkListLength(LinkList L)
{
    LinkList p;
    p = L->Next;
    int i = 0;

    while(p)
    {
        p = p->Next;
        i++;
    }
    printf("\n链表长度为:%d", i);
    return i;
}

/* 获取中间结点 */
Status GetCenterElem(LinkList L, int i, ElemType *e)
{
    LinkList p;
    p = L->Next;
    for(int j = 0; j < i/2; j++)
    {
        p = p->Next;
    }
    *e = p->data;
    return OK;
}

/* 尾插法创建单链表 */
void CreateListTail(LinkList *L)
{
    ElemType e;
    LinkList p, r;
    int i = 1;

    *L = (LinkList)malloc(sizeof(Node));
    r = *L;
    printf("输入表中的数据元素,输入 -100 结束!\n");
    while(i)
    {
        scanf("%d", &e);
        if(e == -100)
            i = 0;
        else
        {
            p = (LinkList)malloc(sizeof(Node));
            p->data = e;
            r->Next = p;
            r = p;
        }
        r->Next = NULL;
    }
}

/* 打印表 */
void PrintList(LinkList L)
{
    LinkList p;
    p = L->Next;
    printf("L->");

    while(p)
    {
        printf(" %d->", p->data);
        p = p->Next;
    }
    printf("NULL\n");
}

int main()
{
    /* 选择子函数 */
    int select()
    {
        int s;
        printf("\n输入要操作的序号:\n------------------------------\n");
        printf("1. 单链表建立(尾插法)\n");
        printf("2. 单链表打印\n");
        printf("3. 获取单链表中间结点\n");
        printf("0. 退出\n------------------------------\n");

        for(;;)
        {
            scanf("%d", &s);
            if(s < 0 || s > 3)
                printf("输入错误,重新输入!");
            else
                break;
        }
        return s;
    }

    LinkList L;
    ElemType e;

    for(;;)
    {
        switch(select())
        {
        case 1:
            printf("单链表建立(尾插法)\n");
            CreateListTail(&L);
            break;
        case 2:
            printf("单链表打印如下:\n");
            PrintList(L);
            break;
        case 3:
            printf("获取单链表中间结点:");
            int length = GetLinkListLength(L);
            if(GetCenterElem(L, length, &e) == OK)
                printf("\n \n获取成功!中间结点元素为:%d\n", e);
            break;
        case 0:
            printf("再见!\n");
            return 0;
        }
    }
    return 0;
}

使用快慢指针

使用快慢指针的方法来解决这个问题,快指针每次走 2 个结点,慢指针每次走 1 个结点,当快指针走完,慢指针刚好走到中间,这就是快慢指针的核心思想。

Status GetCenterElem(LinkList L, ElemType *e)
{
    LinkList search, mid;
    mid = search = L->Next;

    while(search->Next != NULL)
    {
        // search 移动的速度是 mid 的两倍
        if(search->Next->Next != NULL)
        {
            search = search->Next->Next;
            mid = mid->Next;
        }
        else
        {
            search = search->Next;
        }
    }

    *e = mid->data;

    return OK;
}

完整代码

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;
typedef int Status;
typedef struct Node
{
    ElemType data;
    struct Node *Next;
} Node;
typedef struct Node *LinkList;

/* 获取中间结点 */
Status GetCenterElem(LinkList L, ElemType *e)
{
    LinkList search, mid;
    mid = search = L->Next;

    while(search->Next != NULL)
    {
        // search 移动的速度是 mid 的两倍
        if(search->Next->Next != NULL)
        {
            search = search->Next->Next;
            mid = mid->Next;
        }
        else
        {
            search = search->Next;
        }
    }

    *e = mid->data;

    return OK;
}

/* 尾插法创建单链表 */
void CreateListTail(LinkList *L)
{
    ElemType e;
    LinkList p, r;
    int i = 1;

    *L = (LinkList)malloc(sizeof(Node));
    r = *L;
    printf("输入表中的数据元素,输入 -100 结束!\n");
    while(i)
    {
        scanf("%d", &e);
        if(e == -100)
            i = 0;
        else
        {
            p = (LinkList)malloc(sizeof(Node));
            p->data = e;
            r->Next = p;
            r = p;
        }
        r->Next = NULL;
    }
}

/* 打印表 */
void PrintList(LinkList L)
{
    LinkList p;
    p = L->Next;
    printf("L->");

    while(p)
    {
        printf(" %d->", p->data);
        p = p->Next;
    }
    printf("NULL\n");
}

int main()
{
    /* 选择子函数 */
    int select()
    {
        int s;
        printf("\n输入要操作的序号:\n------------------------------\n");
        printf("1. 单链表建立(尾插法)\n");
        printf("2. 单链表打印\n");
        printf("3. 获取单链表中间结点\n");
        printf("0. 退出\n------------------------------\n");

        for(;;)
        {
            scanf("%d", &s);
            if(s < 0 || s > 3)
                printf("输入错误,重新输入!");
            else
                break;
        }
        return s;
    }

    LinkList L;
    ElemType e;

    for(;;)
    {
        switch(select())
        {
        case 1:
            printf("单链表建立(尾插法)\n");
            CreateListTail(&L);
            break;
        case 2:
            printf("单链表打印如下:\n");
            PrintList(L);
            break;
        case 3:
            if(GetCenterElem(L, &e) == OK)
                printf("\n \n获取成功!中间结点元素为:%d\n", e);
            break;
        case 0:
            printf("再见!\n");
            return 0;
        }
    }
    return 0;
}