实现删除链表倒数第n个结点,并且返回头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:给定的 n 保证是有效的。
思路:使用两个结点,一个是p,一个是q。先让p向前走n步,然后p和q同时向前走,当p走到头的时候,q即是倒数n+1个结点了。另q.next=q.next.next,则删除了倒数第n个结点。
有两种特殊情况:
1.链表长度小于n,则返回原链表
2.链表长度为n,则返回head.next
代码实现:
/**
* Definition for singly-linked list.--单链表的定义
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode p = head;
int i;
for(i = 0; i < n; i++) //用于判断链表长度,同时让p先走n步
{
p = p.next;
if(p == null)
break;
}
if(i == n - 1 && p ==null) //链表长度为n时,头结点就是倒数第n个结点,删除头结点即可
return head.next;
if(i < n - 1 && p == null) //如果链表长度小于n,则不需要删除结点,返回原链表即可
return head;
ListNode q = head;
while(p.next != null)
{
//这时让p和q同时向前走,直到链表遍历完成
p = p.next;
q = q.next;
}
q.next = q.next.next;
return head;
}
}
网友评论