19.删除链表的倒数第N个节点

佚名 6年前 (2019-05-11) 随笔 1014人围观抢沙发百度已收录

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

 1     private class ListNode {
 2         int val;
 3         ListNode next;        
 4         ListNode(int x) {
 5             val = x;
 6         }
 7     }
 8     //方法一：第一次遍历得到链表的长度L，根据长度值获取顺数的第L-n+1个节点；第二次遍历删除
 9     public ListNode removeNthFromEnd1(ListNode head, int n) {
10         ListNode current = head;
11         int len = 0;
12         while(current != null){
13             len++;
14             current = current.next;
15         }
16         int del = len - n;  //被删除节点的前一个节点
17         int i = 1;
18         current = head;
19         while(true) {
20             if(del == 0) {  //删除首节点情况
21                 return head = head.next;
22             }
23             if(i == del) { //定位到删除节点前一节点，删除其他节点情况
24                 current.next = current.next.next;
25                 return head;
26             }
27             current = current.next;
28             i++;
29         }
30     }
31     //方法二：一次遍历，得到链表长度，同时使用postOrder节点记录倒数的第N+1个节点，然后直接删除第N个节点
32     public ListNode removeNthFromEnd2(ListNode head, int n) {
33         ListNode preOrder = head;
34         ListNode postOrder = head;
35         int len = 0;
36         while(preOrder != null) {
37             len++;
38             if(len > n+1) {  //记录倒数的第N+1个节点
39                 postOrder = postOrder.next;
40             }
41             preOrder = preOrder.next;
42         }
43         if(len == n) {  //删除头结点情况
44             head = head.next;
45         }else {            //删除非头结点
46             postOrder.next = postOrder.next.next;
47         }
48         return head;
49     }