第四节：链表相关(删除倒数第N节点、相邻位置交换)

一. 删除倒数第N个节点

一. 题目描述

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

    示例：

    leetcode地址：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

    难度：【中等】

二. 思路分析

     (经典的链表问题，双指针(快慢指针)解决)

    (1).创建虚拟节点dummy, 即它的next指向head第一个节点 【主要为了方便处理边界情况,dummy是头节点head的前一个节点】

    (2).创建快慢双指针，等于dummy

    (3). 让fast快指针先移动n+1步，然后让fast和slow指针同时移动, 直到fast为空  【精髓！】

        此时slow指针恰巧指向被删除节点的前一个节点

    (4). 修改slow指针的指向，达到删除的目的

    (5). 返回头节点，即dummy.next

三. 代码实操

class ListNode {
	val: number;
	next: ListNode | null;
	constructor(val?: number, next?: ListNode | null) {
		this.val = val === undefined ? 0 : val;
		this.next = next === undefined ? null : next;
	}
}

/**
 * 删除链表倒数第N个节点
 * @param head 头节点
 * @param n 需要被删除的倒数第n个节点
 * @returns 返回头节点
 */
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
	//1.创建虚拟节点
	let dummy = new ListNode(-1);
	dummy.next = head;

	//2.创建双指针(快慢指针)
	let fast = dummy;
	let slow = dummy;

	//3.让fast快指针移动n+1步
	for (let i = 0; i <= n; i++) {
		fast = fast.next!;
	}

	//4.让fast和slow指针同时移动,直到fast为空(即超过了最后一个元素)
	while (fast) {
		fast = fast.next!;
		slow = slow.next!;
	}

	//5.此时slow指针恰巧指向被删除节点的前一个节点
	slow.next = slow.next?.next!;

	//6.返回头节点
	return dummy.next;
}

二. 链表相邻位置两两交换

一. 题目描述

 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

 leetcode：https://leetcode.cn/problems/swap-nodes-in-pairs/description/

 难度：【中等】

二. 思路分析

(1). 创建虚拟节点dummy节点,指向head节点

(2). 创建一个current节点,默认指向虚拟节点（这里因为有虚拟节点，所以可以直接调用next）

(3). 遍历节点(接下来两个节点都存在，一直循环)

      A. 取出接下来的两个节点

      B. 交换位置

      C. current赋值，开始下一轮循环

(4).返回头节点

三. 代码实操

class ListNode {
	val: number;
	next: ListNode | null;
	constructor(val?: number, next?: ListNode | null) {
		this.val = val === undefined ? 0 : val;
		this.next = next === undefined ? null : next;
	}
}

/**
 * 链表相邻位置的两两交换
 * @param head 头节点
 * @returns  头节点
 */
function swapPairs(head: ListNode | null): ListNode | null {
	// 1. 创建虚拟节点
	let dummy = new ListNode(-1);
	dummy.next = head;

	//2. 创建current节点,指向虚拟节点
	let current = dummy;

	//3. 循环进行两两交换
	while (current.next && current.next.next) {
		let node1 = current.next;
		let node2 = current.next.next;

		//交换node1和node2位置
		current.next = node2;
		node1.next = node2.next;
		node2.next = node1;

		//开始下一次交换
		current = node1;
	}

	return dummy.next;
}

三. 

!

• 作       者 : Yaopengfei(姚鹏飞)
• 博客地址 : http://www.cnblogs.com/yaopengfei/
• 声     明1 : 如有错误，欢迎讨论，请勿谩骂^_^。
• 声     明2 : 原创博客请在转载时保留原文链接或在文章开头加上本人博客地址，否则保留追究法律责任的权利。