设计一个复杂度为n的算法找到链表倒数第m个元素。最后一个元素

[问答题]

设计一个复杂度为n的算法找到链表倒数第m个元素。最后一个元素假定是倒数第0个。

cyanlong

分析：

定义两个链表指针，一个先停在头节点，一个先一直向前走 m 步。这时我们的两个指针一个在后(头节点处)，一个在前(第m个节点处 )，间隔为m。之后，两个指针以步长为1同时向前走，因为这个两个指针在之后同步移动的过程中间隔一直为m，所以当前面的指针到达尾节点时，后面的指针就是倒数第m个节点。

//节点定义：
static class Node{
    int val;
    Node next;
}

//得到倒数第k个节点。
public Node getKth(Node node, int m){
    if (node == null)
         return null;
   Node p1 = node, p2 = node;
   int index = 0;
    while (p2.next != null){
        if (++index <= m){
            p2 = p2.next;
        } else {
            p1 = p1.next;
            p2 = p2.next;
        }
    }
    if (index < m)  //链表长度小于等于k。
        return null; 
    return p1;   
}

编辑于 2017-01-23 12:31:54 回复(2)

爱学习的猪

1.我们也可以在构造链表时，增加一个变量来维护链表的节点数量，那么节点数为n的链表找到倒数第m个节点，只需从头遍历到第n-m+1个节点，这样时间复杂度还是O(n)的 2，如果链表是双向链表，则直接从后向前遍历到第m+1个节点即可

发表于 2017-03-08 11:05:03 回复(0)

牛客424488379号

elemtype Find(List L ,int m){

List p1 , p2;

int counter;

p1 = p2 =L;

counter = 0 ;

while (p1 && (++counter<=m)) p1 = p1->next; //p1移动到第m个结点

if(counter<=m) return error;//m超过了链表长度，不存在倒数第m个元素

while (p1){ //两个指针同步移动，知道p1到达表尾。

p1 = p1->next;

p2 = p2->next;

}

return p2->data; //此时p2指向倒数第m个元素。

}

发表于 2023-04-24 19:55:09 回复(1)

BugFree

// 因为m可以为0，所以辅助指针temp先走m+1步，然后temp和target同速度前进，
// 当temp=null时，target所指即为倒数第m个元素       
     public static class Node {
		int value;
		Node next;
		public Node(int n) {
			this.value = n;
			this.next = null;
		}
	}
//	查找链表中倒数第m个节点 m>=0
	public static Node searchKthLastNode(Node head, int k) {
		if (head == null || k < 0)
			return head;
		if (k >= getListLength(head))
			return null;
		Node target = head;
		Node temp = head;
		for (int i = 0; i <= k; i++) {
			temp = temp.next;
		}
		// n-k
		while (temp != null) {
			target = target.next;
			temp = temp.next;
		}
		temp = null;
		target.next = null;
		System.out.print("target.value: " + target.value + "  ");
		return target;
	}

编辑于 2017-09-04 22:26:18 回复(0)

提交观点

问题信息

编程基础链表复杂度

上传者：牛100

难度：

4条回答 35收藏 3394浏览

设计一个复杂度为n的算法找到链表倒数第m个元素。最后一个元素

问题信息

热门推荐

相关试题