查找单链表倒数第k个位置上的结点(高效算法)

题目

已知一个带有表头结点的单链表,结点结构为

data link

在不改变链表的前提下,设计一个尽可能高效的算法,查找链表中倒数第kkk个位置上的结点。若查找成功,算法输出该结点的data域的值,并返回111,否则,只返回000。

分析

解决这个题目的方法有很多种:

  1. 采用两遍或多遍扫描链表,先得到链表长度,再顺序扫描到LKL-KL−K位置;
  2. 采用递归算法,在递归返回位置计数,计到kkk位置;
  3. 辅助数组;

但上述这些方法都不是最优的,我们可以定义两个指针*p, *q*p*q之间间隔k个结点,且*p在前*q在后,当*q指向尾结点时,由于*p, *q间隔k个结点,所以*p指向的节点就是倒数第k个结点,因此可以先将*q向后移动k个位置,再将*p, *q同时向后移动,直至*q移动到尾结点处。以上过程,只需扫描一遍链表,为最有算法。

代码
#include<iostream>
#include<stdio.h>
using namespace std;

struct LNode{
    int data;
    LNode *next;
};

int BackLocate(LNode L, int k){
    LNode *p, *q;
    int count = 0;
    p = q = L.next;
    while(q != NULL){
        count++;
        if(count > k)
            p = p->next;
        q = q->next;
    }
    if(k > count)	//当K大于链表长度时,返回-1
        return -1;
    return p->data;
}

int main(){
    int a[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    LNode L, *r;
    r = NULL;
    for(int i=0; i<10; i++){	//尾插法建立链表
        LNode *p;
        p = new LNode;
        p->data = a[i];
        if(r == NULL){
            L.next = p;
            r = p;
        }
        else{
            r->next = p;
            r = p;
        }
    }
    r->next = NULL;
    printf("%d\n", BackLocate(L, 3));
}
上一篇:单链表的查找、建立操作(C语言)


下一篇:线段树