老青菜

剑指offer-链表的倒数第k个节点

2017-01-17

题目

输入一个单链表,输出该链表中倒数第k个结点。

分析

为了能够只遍历一次就能找到倒数第k个节点,我们使用一个巧妙的方法:

  1. 定义两个指针,第一个指针a从链表的头指针开始遍历向后走k-1步,第二个指针b保持不动,这两个指针始终保留k-1
  2. 从第k步开始,第二个指针b从链表的头指针开始向后遍历。
  3. 由于两个指针的距离保持在k-1,当第一个指针a到达链表的尾结点时,第二个指针b指针正好是倒数第k个结点。

实现


//链表节点
typedef struct _ZHNode {
    struct _ZHNode *next;
    int data;
}ZHNode;

//查找倒数第k个节点
ZHNode* findLastNode(ZHNode *hNode, int k) {
    //链表为空,或者只有一个节点
    if (hNode == NULL || hNode->next == NULL) {
        return hNode;
    }
    //定义两个节点指针
    ZHNode *firstNode = hNode;
    ZHNode *secondNode = NULL;
    if (k>1) {
        //第一个节点先走k步
        for (int i=0; i<k-1; i++) {
            firstNode = firstNode->next;
        }
    }
    //步数太长,第一个节点走完了
    if (firstNode == NULL) {
        return NULL;
    }
    //第一个节点正常走完k步,记录第二个节点
    secondNode = hNode;
    //开始循环,firstNode 往后走 k步
    while (firstNode->next != NULL) {
        //first node向后走一步,second node向后走一步
        firstNode = firstNode->next;
        secondNode = secondNode->next;
    }
    return secondNode;
}

//添加测试链表数据
ZHNode *hNode = malloc(sizeof(ZHNode));
hNode->data = 1;
ZHNode *lastNode = hNode;
for (int i=2; i<=10; i++) {
    ZHNode *nextNode = malloc(sizeof(ZHNode));
    nextNode->data = i;
    lastNode->next = nextNode;
    lastNode = nextNode;
}
//测试结果
findLastNode(hNode, 0);
findLastNode(hNode, 1);
findLastNode(hNode, 2);
findLastNode(hNode, 9);
findLastNode(hNode, 10);
findLastNode(hNode, 11);

使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章