本文共 3043 字,大约阅读时间需要 10 分钟。
既然要求必须用链表,那么先用尾插法建立单向链表,这道题目的特殊性给了链表长度 n,那么遍历 n - k + 1 次就是链表中的倒数第k个。
#include#include using namespace std;typedef struct ListNode{ int num; ListNode* next;}ListNode, *LinkList;void CreateList(LinkList &L, int n){ L = (LinkList)malloc(sizeof(ListNode)); //头结点 L -> next = NULL; LinkList l = L; for(int i = 0; i < n; i ++) { LinkList p = (LinkList)malloc(sizeof(ListNode)); int data; cin >> data; //尾插法 p -> num = data; p -> next = NULL; l -> next = p; l = l -> next; }}void FindLast1(LinkList &L, int n, int k){ if(L -> next == NULL || k <= 0 || k > n) { cout << "NULL" << endl; return; } LinkList t = L; for(int i = 0; i <= n - k; i ++) t = t -> next; cout << t->num << endl; }int main(){ int n, k; while(cin >> n >> k) { LinkList L; CreateList(L, n); FindLast1(L, n, k); } return 0;}
既然用了尾插法,那么当然想到了更简单的方法——头插法。头插法就是在头结点后插入该节点,始终把该节点作为第一个节点。尾插法就是在链表的最后一个节点处插入元素,作为最后一个节点。 头插法形成的链表是输入数据的逆序,所以我们只需要遍历 k 次就能得到倒数第 k 个节点了。
#include#include using namespace std;typedef struct ListNode{ int num; ListNode* next;}ListNode, *LinkList;void CreateList(LinkList &L, int n){ L = (LinkList)malloc(sizeof(ListNode)); //头结点 L -> next = NULL; for(int i = 0; i < n; i ++) { LinkList p = (LinkList)malloc(sizeof(ListNode)); int data; cin >> data; //头插法 p -> num = data; p -> next = L -> next; L -> next = p; }}void FindLast2(LinkList &L, int n, int k){ if(L -> next == NULL || k <= 0 || k > n) { cout << "NULL" << endl; return; } LinkList t = L; for(int i = 0; i < k; i ++) t = t -> next; cout << t -> num << endl; }int main(){ int n, k; while(cin >> n >> k) { LinkList L; CreateList(L, n); FindLast2(L, n, k); } return 0;}
设置两个指针先同时指向头结点,p2先走k-1步,然后p1,p2同时走,直到p2->next=NULL,p1所指即为倒数第k个,图示如下。
#include#include using namespace std;typedef struct ListNode{ int num; ListNode* next;}ListNode, *LinkList;void CreateList(LinkList &L, int n){ L = (LinkList)malloc(sizeof(ListNode)); //头结点 L -> next = NULL; LinkList l = L; for(int i = 0; i < n; i ++) { LinkList p = (LinkList)malloc(sizeof(ListNode)); int data; cin >> data; //尾插法 p -> num = data; p -> next = NULL; l -> next = p; l = l -> next; }}void FindLast3(LinkList &L, int n, int k){ if(L -> next == NULL || k <= 0 || k > n) { cout << "NULL" << endl; return; } LinkList p1 = L, p2 = L; for(int i = 0; i < k - 1; i ++) p2 = p2 -> next; while(p2 -> next != NULL) { p1 = p1 -> next; p2 = p2 -> next; } cout << p1 -> num << endl; }int main(){ int n, k; while(cin >> n >> k) { LinkList L; CreateList(L, n); FindLast3(L, n, k); } return 0;}