今日算法之_85_删除链表的倒数第N个节点
前言
Github:https://github.com/HealerJean
1、删除链表的倒数第N个节点
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
说明:给定的 n 保证是有效的。
进阶:你能尝试使用一趟扫描实现吗?
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
1.1、算法1
1.1.1、解题思路
笨办法,先求出有多少个节点count,然后count减去n。
如果为0的是肯定是头节点,直接返回头的next节点即可
否则,我们再次遍历一下,找到n的上一个节点。然后删除即可
1.1.2、算法
/**
* 两次遍历
* 1、第一次遍历求的count的大小
* 2、第二次找到对应位置,然后删除
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
int count = 0;
ListNode node = head;
while (head != null) {
count++;
head = head.next;
}
int diff = count - n;
if (diff == 0) {
return node.next;
}
ListNode listNode = node;
while (diff != 0) {
diff--;
if (diff == 0) {
node.next = node.next.next;
}
node = node.next;
}
return listNode;
}
1.2、算法1
1.2.1、解题思路
使用map装入Listnode,key为节点的索引。接着看代码就知道了
1.2.2、算法
/**
* 使用Map装入ListNode ,Integer记录List的个数
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
Map<Integer, ListNode > map = new HashMap<>();
ListNode node = head;
Integer count = 0 ;
while (head !=null){
map.put(++count, head);
head = head.next;
}
//1、如果是第一个则直接返回
Integer diff = count - n ;
if (diff == 0){
return node.next ;
}
//2、否则找到要删除的前一位,然后删除即可
map.get(diff).next = map.get(diff).next.next;
return node;
}
1.3、测试
@Test
public void test() {
System.out.println(removeNthFromEnd(listNode(), 2));
}
public ListNode listNode() {
// ListNode listNode_5 = new ListNode(5, null);
// ListNode listNode_4 = new ListNode(4, listNode_5);
// ListNode listNode_3 = new ListNode(3, listNode_4);
ListNode listNode_2 = new ListNode(2, null);
ListNode listNode_1 = new ListNode(1, listNode_2);
return listNode_1;
}
public String listNodeStr(ListNode listNode, String str) {
if (listNode == null) {
return str.substring(0, str.lastIndexOf(","));
}
str = str + listNode.val + ",";
return listNodeStr(listNode.next, str);
}
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}