找出单链表中的倒数第k个数

题目：

找出单链表中的倒数第k个数，如给定单链表：0–>1->2–>3–>4–>5->6->7,则单链表中的倒数第3个数为5.

解题思路：

思路1：二次遍历求解

第一次遍历链表求出链表的总长度，第二次遍历到n-k求出链表的的倒数第k个元素。

代码实现：

public static LNode findLastkNode(LNode head,int k){ //求出链表的长度定义一个变量 int count=0; LNode cur=head.next; LNode last = head.next; while (cur!=null){ count++; cur=cur.next; } for (int i = 0; i <count -k ; i++) { last=last.next; } return last; }

思路1：快慢指针法

定义两个指针，第一个slow指向头节点，第二个指针指向fast比slow快k的节点，一直遍历直到fast.next=null时即求出slow.

代码实现：

我就不废话了直接看代码

public static LNode findLastkNode(LNode head,int k){ if (head==null||head.next==null) return head; //定义两个指针 LNode slow,fast; slow=fast=head.next; int i; //求出第fast指向的节点 for ( i = 0; i <k&&fast!=null ; i++) { fast=fast.next; } if (i<k){ return null; } while (fast!=null){ slow=slow.next; fast=fast.next; } return slow; }

打印鏈表

//打印链表 public static void PrintList(LNode head){ for (LNode cur = head.next; cur !=null ; cur=cur.next) { System.out.print(cur.data+""); }

初始化链表调用函数

int i=1; LNode head=new LNode(); head.next=null; LNode temp=null; LNode cur=head; for (; i <8 ; i++) { temp=new LNode(); temp.data=i; temp.next=null; cur.next=temp; cur=temp; } System.out.print("链表 :"); PrintList(head); LNode lastkNode = findLastkNode(head, 3); System.out.println("\n第3个节点为 "+lastkNode.data);

結果