首页 > 代码库 > 链表 2.2

链表 2.2

2024-07-23 06:47:24   220人阅读

实现一个算法，找出单向链表中倒数第k个结点。

分析：使用相差k个位置的两个指针，以相同的速度遍历链表，当快指针为空时，慢指针刚好指向链表的倒数第k个结点。时间复杂度O(n)，空间复杂度O(1)。

 1 #include <iostream> 2 #include <fstream> 3 #include <assert.h> 4  5 using namespace std; 6  7 struct Node { 8     Node(): val(0), next(0) {} 9     Node( int aval ): val(aval), next(0) {}10     int val;11     Node *next;12 };13 14 Node* findLastKth( Node *node, int k );15 16 int main( int argc, char *argv[] ) {17     string data_file = "./2.2.txt";18     ifstream ifile( data_file.c_str(), ios::in );19     if( !ifile.is_open() ) {20         fprintf( stderr, "cannot open file: %s\n", data_file.c_str() );21         return -1;22     }23     int n = 0, k = 0;24     while( ifile >>n >>k ) {25         assert( n >= 0 );26         Node guard, *node = &guard;27         for( int i = 0; i < n; ++i ) {28             node->next = new Node();29             node = node->next;30             ifile >>node->val;31             cout <<node->val <<" ";32         }33         cout <<endl;34         node = findLastKth( guard.next, k );35         if( node ) {36             printf( "last %dth node is: %d\n", k, node->val );37         } else {38             printf( "last %dth node is: null", k );39         }40         node = guard.next;41         while( node ) {42             Node *next = node->next;43             delete node;44             node = next;45         }46         cout <<endl <<endl;47     }48     ifile.close();49     return 0;50 }51 52 Node* findLastKth( Node *node, int k ) {53     Node *slow = node, *fast = node;54     for( int i = 0; i < k; ++i ) {55         if( !fast ) { return 0; }56         fast = fast->next;57     }58     while( fast ) {59         slow = slow->next;60         fast = fast->next;61     }62     return slow;63 }

测试文件

0 00 11 011 111 212 01 32 11 32 21 32 31 37 114 54 96 23 45 12 457 214 54 96 23 45 12 457 714 54 96 23 45 12 45

 

链表 2.2


联系
我们