首页 > 试题广场 >

找出单向链表中的一个节点,该节点到尾指针的距离为K

[编程题]找出单向链表中的一个节点,该节点到尾指针的距离为K
  • 热度指数:11158 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
找出单向链表中的一个节点,该节点到尾指针的距离为K。链表的倒数第0个结点为链表的尾指针。要求时间复杂度为O(n)。
链表结点定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
}
链表节点的值初始化为1,2,3,4,5,6,7。

输入描述:
该节点到尾指针的距离K


输出描述:
返回该单向链表的倒数第K个节点,输出节点的值
示例1

输入

2

输出

6

备注:
请自觉实现一个链表,将1到7依次加入链表,然后再寻找倒数第K个节点。要求加节点与找节点的操作复杂度均为O(n)。
/*
链表遍历,p,q指向头结点,
p先走k步,然后p、q一起走 ,直到p为空,q节点即为所求
*/
#include<bits/stdc++.h>
using namespace std;
#define N 1000
struct ListNode {
    int m_nKey;
    ListNode* m_pNext;
    ListNode(int x): m_nKey(x), m_pNext(NULL) {}
};

int main()
{
//    freopen("input.txt", "r", stdin);
    ListNode* list = new ListNode(1);
    ListNode *p = list, *q = list;
    for(int i = 2; i <= 7; i++) {
        ListNode* node = new ListNode(i);
        p->m_pNext = node;
        p = node;
    }
    int k;
    cin >> k;
    p = list;
    q = list;
    while(k--) {
        p = p->m_pNext;
    }
    while(p != NULL) {
        q = q->m_pNext;
        p = p->m_pNext;
    }
    cout << q->m_nKey << endl;
    return 0;
}

发表于 2019-07-14 10:46:57 回复(1)
class Node:
    def __init__(self,x):
        self.val = x
        self.next = None
head = Node(0)
temp = head
for i in range(1,8):
    node = Node(i)
    temp.next = node
    temp = node

first = head.next
i = 0
k = int(input())
while i < k-1:
    first = first.next
    i += 1
slow = head.next
while first.next:
    first = first.next
    slow = slow.next
print(slow.val)

发表于 2019-08-09 10:05:37 回复(1)
思路:
第一次循环遍历得到总长度
第二次遍历计数,直到count(计数值)=总长度-k,然后当前节点即可。

import java.util.Scanner;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Test {
    public static ListNode FindKthToTail(ListNode head,int k) {
    	
        ListNode p;
        int len=0,count=0;
        p=head;  
    	while(p!=null)
        {   
    	    len++;       
            p=p.next;
        }
        p=head;
        while(p!=null){ 
            if(len-k==count)
                return p;
            else 
            {
                count++;
                p=p.next;
            }
        }
        return null;           
    }
    public static void main(String[] args) {
    	Scanner sc=new Scanner(System.in);
    	ListNode head =new ListNode(1);   	
    	ListNode p=null;
    	p=head;
    	p.next=null;
    	for(int i=2;i<8;i++){
    		ListNode q=new ListNode(i);
    		p.next=q;
    		p=q;
    		p.next=null;     		
    	}
    	p=FindKthToTail(head,sc.nextInt());
    	System.out.print(p.val);            
	}
}

发表于 2019-09-26 15:26:20 回复(0)
function LinkFun(){
    let Node = function(val){
        this.val = val;
        this.next = null
    }
    let head = null;
    let length = 0
    this.append = function(val){
        let node = new Node(val);
        let cur ;
        if(head == null){
            head = node
        }else{
            cur = head;
            while(cur.next){
                cur = cur.next
            }
            cur.next =node
        }
        length ++
    }
    this.getHead = function(){
        return head
    }
    this.getLength = function(){
        return length
    }
}
let arr = [];
for(let i = 1;i<8;i++){
    arr.push(i)
}
let link = new LinkFun();
for(let i = 0;i<7;i++){
    link.append(arr[i])
}

let head = link.getHead()
function getNode(head){
    let arr = [],pNode = head;
    while(pNode){
        arr.unshift( pNode.val )
        pNode = pNode.next
    }
    return arr
}
let res = getNode(head)
let n = readline()
print(res[n-1])


发表于 2019-08-25 10:10:57 回复(0)
采用快慢指针求解
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        ListNode head = new ListNode(0);
        ListNode p = head;
        for (int i = 1; i <= 7; ++i) {
            ListNode newNode = new ListNode(i);
            p.next = newNode;
            p = p.next;
        }
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine().trim());
        head = head.next;
        ListNode first = head, second = head;
        int i = 0;
        // 先让first指针先走k-1步
        while(i < k - 1){
            first = first.next;
            i ++;
        }
        // 然后first和second一起走,当first走到了最后一个节点,second就走到了倒数第k个节点
        while(first.next != null){
            first = first.next;
            second = second.next;
        }
        System.out.println(second.val);
    }
}


发表于 2021-02-27 16:14:46 回复(2)
#include <bits/stdc++.h>
using namespace std;
struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};
ListNode* creatList(const vector<int> &arr){
    if(arr.empty())
        return nullptr;
    ListNode *head,*cur,*pre;
    head=new ListNode;
    head->m_nKey=arr[1];
    head->m_pNext=nullptr;
    pre=head;
    for(int i=2;i<arr.size();i++){
        cur=new ListNode;
        cur->m_nKey=arr[i];
        cur->m_pNext=nullptr;
        pre->m_pNext=cur;
        pre=pre->m_pNext;
    }
    ListNode *p=head;
    return head;
}
int solve(ListNode *head,int k){
    ListNode *slow,*fast;
    slow=fast=head;
    for(int i=1;i<=k;i++)
        fast=fast->m_pNext;
    while(fast){
        fast=fast->m_pNext;
        slow=slow->m_pNext;
    }
    return slow->m_nKey;
}
int main(){
    vector<int> arr(8,0);
    int k;
    for(int i=1;i<=7;i++)
        arr[i]=i;
    cin>>k;
    ListNode *head=creatList(arr);
    cout<<solve(head,k);
    return 0;
}

发表于 2019-10-20 16:53:47 回复(0)
class ListNode():
    def __init__(self, val):
        self.val = val
        self.next = None
    
    def __str__(self):
        return str(self.val)
    
def create_list_table(data):
    #data = [1,2,3,4,5,6,7]
    if not data:
        return None
    p = ListNode(data[0])
    for i in data[1:][::-1]:
        q = ListNode(i)
        q.next = p.next
        p.next = q
    return p

def find_lastK_point(linklist, k):
    if not linklist or k < 0:
        raise ValueError('')
    front, behind = linklist, linklist
    for _ in range(k):
        if not front and not front.next:
            raise ValueError('')
        front = front.next
    while front:
        front = front.next
        behind = behind.next
    print(behind)

p = create_list_table([1, 2, 3, 4, 5, 6,7])
find_lastK_point(p, int(input()))
剑指offer原题
发表于 2019-10-10 20:00:38 回复(0)
 var createList =function(value,next){
    this.value=value;
    this.next = next;
  }
  var ary1=[1,2,3,4,5,6,7];
  var listNodes = [];
  var getList=function (ary){;
    for(var i=ary.length-1;i>=0;i--){
      if(i==ary.length-1){
        var curNode= null;
        curNode = new createList(ary[i],curNode);
        listNodes.push(curNode);
      }else {
        var  curNode = new createList(ary[i],curNode);
        listNodes.push(curNode)
      }
    }
    return listNodes;
  }
  line=readline()
  var ary = getList(ary1);
  print (ary[line-1].value);

首先创建一个node类,然后创建一个链表,next指向下一个Node类。
发表于 2019-09-12 15:51:52 回复(0)
思路:
先用尾插法构建链表L;
然后用两个指针p,q指向L;
先让p走k步,然后再让p、q一起往后走,直至p走到链表尾
此时q指向的即为倒数第k个节点
#include<bits/stdc++.h>
using namespace std;

typedef struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
}LinkList;

void CreateList(LinkList *&L,int a[],int n){
    LinkList *s,*r;
    int i;
    L = (LinkList*)malloc(sizeof(struct ListNode));
    r = L;
    for(i=0;i<n;i++){
        s = (LinkList*)malloc(sizeof(struct ListNode));
        s->m_nKey = a[i];
        r->m_pNext = s;
        r = s;
    }
    r->m_pNext = NULL;
}

int main(){
    LinkList *L,*p,*q;
    int k;
    int a[8] = {1,2,3,4,5,6,7};
    CreateList(L,a,7);
    //L = L->m_pNext;
    cin>>k;
    p = L,q = L;
    while(k>0&&p){
        p = p->m_pNext;
        k--;
    }
    if(k>0&&p==NULL)
        cout<<"NULL";
    while(p){
        p = p->m_pNext;
        q = q->m_pNext;
    }
    cout<<q->m_nKey;
}               


发表于 2019-09-05 17:19:39 回复(0)
import java.util.*;
class ListNode{
    int val;
    ListNode next = null;
    ListNode(int val){
        this.val=val;
    }
}

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        ListNode list = create();
        for(int i=0;i<7-k;i++){
            list=list.next;
        }
        System.out.print(list.val);
    }
    public static ListNode create(){
        ListNode preList=new ListNode(0);
        ListNode list=preList;
        for(int i=0;i<7;i++){
            list.next=new ListNode(i+1);
            list=list.next;
        }
        return preList.next;
    }
}
任意长度的链表倒数k个的方法。
import java.util.*;
class ListNode{
    int val;
    ListNode next = null;
    ListNode(int val){
        this.val=val;
    }
}

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        ListNode list = create(); 
        ListNode lowList = list;
        for(int i=0;i<k;i++){
            list=list.next;
        }
        while(list!=null) {
        	lowList=lowList.next;
        	list = list.next;
        }
        System.out.print(lowList.val);
    }
    public static ListNode create(){
        ListNode preList=new ListNode(0);
        ListNode list=preList;
        while(sc.hasNext()){
            list.next=new ListNode(sc.nextInt());
            list=list.next;
        }
        return preList.next;
    }
}


编辑于 2019-08-28 13:36:22 回复(1)
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Singlelist single=new Singlelist();
		for (int i = 1; i <=7; i++) {
			ListNode list=new ListNode(i);
			single.addNodeList(list);
		}
		Scanner sc=new Scanner(System.in);
		System.out.println(findLastIndexNode(sc.nextInt(),single.getHead()));
	}
	
	public static ListNode findLastIndexNode(int index,ListNode head) {
		if(head.m_pNext==null) {
			return null;
		}
		int size=getLenght(head);
		if(index<=0||index>size) {
			return null;
		}
		ListNode temp=head.m_pNext;
		for (int i = 0; i < size-index; i++) {
			temp=temp.m_pNext;
		}
		return temp;
	}
	
	//查询长度
	public static int getLenght(ListNode head) {
		if(head.m_pNext==null) {
			return 0;//空链表
		}
		int length=0;
		ListNode temp=head.m_pNext;
		while(temp!=null) {
			length++;
			temp=temp.m_pNext;
		}
		return length;
	}
}

class Singlelist {
	private ListNode head=new ListNode(0);
	
	public ListNode getHead() {//返回头节点
		return head;
	}
	//添加
	public void addNodeList(ListNode listNode) {
		ListNode temp=head;
		boolean flag=false;// 默认false表示可添加
		while (true) {
			if(temp.m_pNext==null) {//说名为空
				break;
			}
			if(temp.m_pNext.m_nKey>listNode.m_nKey) {
				break;
			}else if(temp.m_pNext.m_nKey==listNode.m_nKey) {
				flag=true;//说明编号存在1
			}
			temp=temp.m_pNext;//后移遍历
		}
		if(flag) {
			System.out.println("已存在");
		}else{
			listNode.m_pNext=temp.m_pNext;
			temp.m_pNext=listNode;
		}
	}

	//显示
	public void show() {
		if(head.m_pNext==null) {
			System.out.println("链表为空");
			return;
		}
		ListNode temp=head.m_pNext;
		while(true) {
			if(temp==null) {
				break;
			}
			System.out.println(temp.m_nKey);
			temp=temp.m_pNext;
		}
	}
}

class ListNode{//定义ListNode , 每个ListNode 对象就是一个节点
	 Integer m_nKey;
	 ListNode m_pNext;
	public ListNode(Integer m_nKey) {
		super();
		this.m_nKey = m_nKey;
	}
	@Override
	public String toString() {
		return m_nKey +"";
	}
}


发表于 2019-08-18 12:26:46 回复(0)
import java.util.Scanner;
class ListNode{
    int m_nKey;
    ListNode m_pNext;
}
public class Main{
    public static void main(String[] args){
        ListNode list=new ListNode();
        list.m_nKey=1;
        ListNode last=list;
        for(int i=1;i<7;i++){       //将1到7依次加入到链表
            last.m_pNext=new ListNode();
            last.m_pNext.m_nKey=i+1;
            last=last.m_pNext;
        }
        Scanner in=new Scanner(System.in);  //输入k
        int k=in.nextInt();
        if(k==0){                           //k=0,链表尾就是
            System.out.println(last.m_nKey);
        }else{
            ListNode p=list;     //双指针法
            ListNode q=list;
            for(int i=0;i<k-1;i++){     //一个指针先走k-1步
                p=p.m_pNext;
            }
            while(p.m_pNext!=null){     //第二个指针开始和第一个指针一起走
                p=p.m_pNext;
                q=q.m_pNext;            //当第一个指针到链表尾时,第二个指针指的结点就是倒数第k个结点
            }
            System.out.println(q.m_nKey);
        }
    }
}

编辑于 2019-10-31 16:48:51 回复(2)
#include <bits/stdc++.h>
using namespace std;

struct ListNode{
    int m_nKey;
    ListNode *m_pNext;
    ListNode(int x):m_nKey(x),m_pNext(NULL){}
};

int main(){
    int k;
    ListNode *L = new ListNode(1);
    ListNode *p = L, *q = L;
    for(int i=2;i<=7;i++){
        ListNode *t = new ListNode(i);
        p->m_pNext = t;
        p = t;
    }
    cin>>k;
    p = q = L;
    while(k--)
        q = q->m_pNext;
    while(q!=NULL){
        p = p->m_pNext;
        q = q->m_pNext;
    }
    cout<<p->m_nKey<<endl;
    return 0;
}

发表于 2019-08-12 08:21:52 回复(0)
#include <stdio.h>
#include<stdlib.h>
struct ListNode
{
int m_nKey;
struct ListNode* m_pNext;
};
void sListNode(struct ListNode** head,int x)
{
    struct ListNode* newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
    newnode->m_nKey=x;
    newnode->m_pNext=NULL;
    struct ListNode* cur=*head;
    if(*head==NULL)
    {
        *head=newnode;
    }
    else{
        while(cur->m_pNext)
        {
            cur=cur->m_pNext;
        }
        cur->m_pNext=newnode;
    }
}
int  sListnode(struct ListNode** phead,int k )
{
    //利用快慢指针
 struct ListNode* list,*next;
 list=*phead,next=*phead;
 while(k--)//先走k步
 {
    next=next->m_pNext;
 }
 while(next)//再走到空指针,慢指针正好走到倒数的k位
 {
    list=list->m_pNext;
    next=next->m_pNext;
 }
 return list->m_nKey;
}
int main()
{
    struct ListNode* head=NULL;
sListNode(&head,1);//编写插入链表的函数
sListNode(&head,2);
sListNode(&head,3);
sListNode(&head,4);
sListNode(&head,5);
sListNode(&head,6);
sListNode(&head,7);
int k=0;
scanf("%d",&k);
int kNode=sListnode(&head,k);//编写返回倒数k为的数
printf("%d",kNode);
return 0;
}
发表于 2023-08-11 20:10:45 回复(0)
投机取巧
#include "iostream"
using namespace std;
int main()
{
    int k;
    cin>>k;
    cout<<8-k<<endl;
    return 0;
}


发表于 2022-10-04 15:36:29 回复(0)
import java.util.*; import java.io.*; public class Main{ static class ListNode{ int val; ListNode next; public ListNode(int val){ this.val = val; this.next = null; } } public static void main(String[] args) throws IOException{ ListNode head = new ListNode(0); ListNode p = head; for(int i=1;i<=7;++i){ ListNode newNode = new ListNode(i); p.next = newNode; p = p.next; } BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int k = Integer.parseInt(reader.readLine()); int n = dfs(head.next, k); } public static int dfs(ListNode head, int k){ if(head==null) return 0; int cnt = 1+dfs(head.next, k); if(cnt==k) System.out.println(head.val); return cnt; } }
编辑于 2022-04-17 15:55:59 回复(0)
#include<iostream>
using namespace std;
typedef struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
}Node;
class List {
private:
    ListNode* head;
    ListNode* rear;

public:
    List()
    {
        rear = new ListNode();
        for (int i = 7; i >0; i--)
        {
            ListNode* a=new ListNode();
            a->m_nKey = i;
            if (i == 7)
            {
                a->m_pNext = rear;
                head = a;
            }
            else
                a->m_pNext = head;
            head = a;
        }
    }
    ListNode* getListNode(int m)
    {

        ListNode* cur = head;
        ListNode* nex = cur->m_pNext;
        ListNode* pre = NULL;
        int i = 0;
        while (cur != rear)
        {
            i++;
            cur->m_pNext = pre;
            pre = cur;
            cur = nex;
            nex = nex->m_pNext;
        }
        if (m > i)
            return rear;
        rear->m_pNext = pre;
        for (i=0; i < m; i++)
        {
            if(rear)
                rear = rear->m_pNext;
            if (i == m - 1)
            {
                break;
            }
        }
      return rear;
    }
};
int main()
{
    List a;
    int b;
    cin >> b;
    ListNode *m=a.getListNode(b);
    cout << m->m_nKey;
    return 0;
}

发表于 2022-02-26 14:29:12 回复(0)
import java.util.*;
public class Main{
    static class ListNode{
        int value;
        ListNode next;
        ListNode(int value){
            this.value = value;
        }
    }
    public static void main(String[] args){
        ListNode head = createList();
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        ListNode KthNode = findKthNode(head, k);
        System.out.print(KthNode.value);
    }
    
    public static ListNode findKthNode(ListNode head, int k){
        if(head == null || k < 0 )
            return null;
        ListNode fast = head;
        ListNode slow = head;
        
        for(int i = 0; i < k; i++){
            if(fast == null)
                return head;
            fast = fast.next;
        }
        
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    
    public static ListNode createList(){
        ListNode head = new ListNode(1);
        ListNode cur = head;
        for(int i = 2; i < 8; i++){
            cur.next = new ListNode(i);
            cur = cur.next;
        }
        return head;
    }
}

发表于 2021-09-05 23:56:04 回复(0)
class ListNode:
    def __init__(self,x):
        self.val = x
        self.next = None
        
head = ListNode(0)
node = ListNode(0)
head.next = node
for i in range(7):
    node.val = i+1
    if(i <6):
        node.next = ListNode(0)
        node = node.next    
# 目前链表创建是对的

k = int(input())
if(k == 1):
    print(node.val)
    exit(0)
    
m = k-1 
node = head.next
while(m > 0):
    if(node.next != None):
        node = node.next
        m -= 1
    else:
        print(None)
res = head.next
while(node.next != None):
    res = res.next
    node = node.next
print(res.val)
发表于 2021-06-29 08:48:10 回复(0)
小菜一碟
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine().trim());
        System.out.println(7-k+1);
    }
}


发表于 2021-05-31 21:30:40 回复(0)