输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
方式一:
思路:首先计算出整个链表的长度,然后根据计算出从前往后遍历的时候,遍历到倒数第k个节点需要多少次,即newCount = count - k + 1次,如果newCount==1的时候,那么说明第一个节点就是需要的,如果不是,则继续遍历,每次newCount-1,并且当newCount=1的时候,就得到需要的节点,在得到需要的节点的时候,需要得到的是一个从该节点开始的链表,所以在每次循环newCount-1的时候,需要保存当前节点的next节点,然后将当前节点的next置为null
public ListNode getKthFromEnd(ListNode head, int k) {
if (head == null) {
return null;
}
if (head.next == null && k > 1) {
return null;
}
int count = 1;
ListNode next = head.next;
while (next != null) {
count++;
next = next.next;
}
int newCount = count - k + 1;
if (newCount == 1) {
return head;
}
while (head.next != null) {
newCount--;
ListNode newNode = head.next;
head.next = null;
head = newNode;
if (newCount == 1) {
break;
}
}
return head;
}
方式二:
public ListNode getKthFromEnd(ListNode head, int k) {
if (head == null)
return null;
ListNode P1 = head;
// 当k--之后依然大于0,则将P1=P1.next
while (P1 != null && k-- > 0)
P1 = P1.next;
if (k > 0)
return null;
ListNode P2 = head;
// 这里的P1中的节点个数其实就是通过遍历得到从前往后一直到目标节点的个数
// 所以对P1进行循环遍历,然后再对P2的这个完整链表进行遍历
// 当P1最后为null的时候,也就是到了目标节点
while (P1 != null) {
P1 = P1.next;
P2 = P2.next;
}
return P2;
}
网友评论