首页 > 其他 > 详细

Interview----链表的倒数第K个元素

时间:2014-03-06 00:12:56      阅读:505      评论:0      收藏:0      [点我收藏+]

这个题虽然简单,但是一定要细心,bug-free 能力很重要。

分析: 如果不知道链表的长度,可以采用双指针的方法,让一个指针先走 k 步,然后两个指针同时走,

前面的指针变成 NULL时, 第一个指针即是倒数第k 个节点。。

但是,考虑 k < 0, k > length 等情况。。


关于双指针的另一个典型例题就是 求两链表是否相交,见 http://blog.csdn.net/shoulinjun/article/details/20127223


// copyright @ L.J.SHOU Mar.05, 2014
// find the last kth node in a list
#include <iostream>
#include <cassert>
using namespace std;

struct ListNode{
  int val;
  ListNode *next;
  ListNode(int x):val(x), next(NULL){}
};

ListNode* LastKthNode(ListNode *list, int k)
{
  assert(k >= 0);
  if(k == 0 || list == NULL)
    return NULL;

  ListNode *p(list);
  for(; k>0 && p; --k)
	p = p->next;

  if(k > 0) // list length less than k
    return NULL;

  while(p)
  {
    p = p->next;
	list = list->next;
  }
  
  return list;
}

int main(void)
{
  ListNode *list(NULL), *node(NULL);

  list = new ListNode(1);
  list->next = new ListNode(2);
  list->next->next = new ListNode(3);

  node = LastKthNode(list, 30);
  if(node != NULL)
    cout << "node is : " << node->val << endl;

  while(list){
    node = list->next;
	delete list;
	list = node;
  }

  return 0;
}


Interview----链表的倒数第K个元素,布布扣,bubuko.com

Interview----链表的倒数第K个元素

原文:http://blog.csdn.net/shoulinjun/article/details/20571009

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!