1.题目描述
Given a linked list, remove the n -th node from the end of list and return its head.
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Follow up(进阶):
Could you do this in one pass?
你能尝试使用一趟扫描实现吗?
2.Solutions
快慢指针(双指针),把慢指针定位到要删除节点的前面就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
public static void (String[] args) { ListNode head = new ListNode(1 ); ListNode node = head; int i = head.val; while (++i<6 ){ node.next = new ListNode(i); node = node.next; } node = removeNthFromEnd(head,1 ); while (node!=null ){ System.out.print(node.val+" " ); node = node.next; } } public static ListNode removeNthFromEnd (ListNode head, int n) { ListNode start = new ListNode(0 ); start.next = head; ListNode slow = start,fast = start; for (int i = 0 ; i <= n; i++) { fast = fast.next; } while (fast!=null ){ slow = slow.next; fast = fast.next; } slow.next = slow.next.next; return start.next; }
(完)
近期评论