class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if (k < 1) { return 0; } if (pListHead == NULL) { return 0; } ListNode* now = pListHead; ListNode* dk = pListHead; for (int i = 0; i < k - 1; i++) { now = now->next; if (now == NULL) { return now; } } while (now->next != NULL) { now = now->next; dk = dk->next; } return dk; } };
时间复杂度O(n),一次遍历即可 public class Solution { public ListNode FindKthToTail(ListNode head,int k) { ListNode pre=null,p=null; //两个指针都指向头结点 p=head; pre=head; //记录k值 int a=k; //记录节点的个数 int count=0; //p指针先跑,并且记录节点数,当p指针跑了k-1个节点后,pre指针开始跑, //当p指针跑到最后时,pre所指指针就是倒数第k个节点 while(p!=null){ p=p.next; count++; if(k<1){ pre=pre.next; } k--; } //如果节点个数小于所求的倒数第k个节点,则返回空 if(count<a) return null; return pre; } }
if(head == null || k ==0 ){ return null; } //可以先把链表反转,然后找出第k个 Stack<ListNode> stack = new Stack<ListNode>(); int count = 0; while(head != null){ stack.push(head); head = head.next; count++; } if(count < k){ return null; } ListNode knode = null; for(int i = 0; i < k; i++){ knode = stack.pop(); } return knode;
class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if(pListHead==NULL||k==0) return NULL; ListNode*pTail=pListHead,*pHead=pListHead; for(int i=1;i<k;++i) { if(pHead->next!=NULL) pHead=pHead->next; else return NULL; } while(pHead->next!=NULL) { pHead=pHead->next; pTail=pTail->next; } return pTail; } };
public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if(head == null) return null; int count = 0; ListNode temp = head; for (int i = 0; temp != null; temp = temp.next) { count++; } if(k>count) return null; System.out.println(count); //一共有count个,倒数第k个就是正数第count-k+1,下标是count-k for(int i = 0;i<count-k;i++){ head = head.next; } return head; } }
public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if(k<1) return null; Q<ListNode> q = new Q<ListNode>(k); while(head!=null){ q.add(head); head = head.next; } return q.get(); } } class Q<T>{ private Object[] arr; private int index = 0; public Q(int l){ arr = new Object[l]; } public void add(T t){ arr[index++] = t; if(index == arr.length) index = 0; } public T get(){ return (T)arr[index]; } }
class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if(pListHead==NULL||k<=0)//如果输入空链表或k<=0 return NULL; stack<ListNode*> stk; ListNode* p=pListHead; while(p!=NULL){ stk.push(p); p=p->next; } if(stk.size()>=k){ //如果k的值大于链表中的元素数目 while((--k)>0){ stk.pop(); } return stk.top(); }else return NULL; } }
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindKthToTail(ListNode head, int k) { if (head == null || k <= 0) { return null; } ListNode slow = head; ListNode fast = head; for (int i = 1; i < k; i++) { if (fast.next == null) { return null; } fast = fast.next; } while (fast.next != null) { fast = fast.next; slow = slow.next; } return slow; } }
class Solution: def FindKthToTail(self, head, k): # write code here if head==None or k<=0: return None #设置两个指针,p2指针先走(k-1)步,然后再一起走,当p2为最后一个时,p1就为倒数第k个 数 p2=head p1=head #p2先走,走k-1步,如果k大于链表长度则返回 空,否则的话继续走 while k>1: if p2.next!=None: p2=p2.next k-=1 else: return None #两个指针一起 走,一直到p2为最后一个,p1即为所求 while p2.next!=None: p1=p1.next p2=p2.next return p1
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(k==0) return null; //判断k为0,返回null的情况
ListNode t = head; //处理长度的第一个指针
int N = 0; //链表长度
ListNode ln= null; //记录距离结尾K长度的node
while(t!=null){
N ++;
if(N == k) ln = head;//当长度超过k的时候,才有值
else if(N>k) ln = ln.next; //当N长度大于k的时候,每一次for循环前移
t = t.next; //处理长度的指针前移
}
return ln; //for循环结束,得到的距离k的Node,可以为空
}
}
//用栈的先进后出特性来做,测试通过 import java.util.Stack; public class Solution { public ListNode FindKthToTail(ListNode head,int k) { Stack<ListNode> stack=new Stack<ListNode>(); ListNode list=null; ListNode tmp=head; int n=0; while(tmp!=null){ //先判断链表是否具有k个节点 tmp=tmp.next; n++; } if(n<k){ //少于k个节点返回null return list; } while(head!=null){ //大于等于k个节点,则全压入栈,再出栈k次 stack.push(head); head=head.next; } for(int j=k;j>0;j--){ list=stack.pop(); } return list; } }
import java.util.Stack; public class Solution { //通过一个辅助栈,利用栈的后进先出特点 //所有结点进栈,再出栈k个 public ListNode FindKthToTail(ListNode head,int k) { if(head==null){ return null; } if(k<0){ return null; } Stack <ListNode> stack=new Stack<ListNode> (); ListNode nodek=null; //记录第k个结点 ListNode current =head; int size=0;//记录结点的个数 while(current!=null){ stack.push(current); current=current.next; size++; } if(k>size){ return null; } for(int i=0;i<k;i++){ nodek= stack.pop(); } return nodek; } }
设置两个指针 fast 、slow,fast先走k步,如果走不到第k步(nullptr节点是可以走到的,但是nullptr节点没有next,所以只能走到nullptr),说明链表长度不够k,直接返回nullptr;然后,令 fast 和 slow 开始同步往下移动,直到 fast 移动到nullptr,此时slow就是倒数第 k 个节点的,返回即可。
code:
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(pListHead == nullptr || k < 1){
return nullptr;
}
ListNode *pre = pListHead;
ListNode *last = pListHead;
while(k > 0){
if(last == nullptr){
return nullptr;
}
last = last->next;
k--;
}
while(last != nullptr){
last = last->next;
pre = pre->next;
}
return pre;
}
};
//使用Vector做中间存储 class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if(pListHead == NULL || k <= 0) return NULL; vector<ListNode *> vec; ListNode *pNode = pListHead; while(pNode != NULL){ vec.push_back(pNode); pNode = pNode->next; } if(vec.size() < k){ return NULL; } return vec[vec.size()-k]; } };
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def FindKthToTail(self, head, k): # write code here front = head later = head for i in range(k): if front==None: return if front.next == None and i==k-1: return head front = front.next while front.next != None: front = front.next later = later.next return later.next