链表反转

第二关——链表反转拓展

1.指定区间反转

Leecode92：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表 。
原题链接

1.1 思路

对应上一篇文章，我们可以分成两种解决办法：头插法、穿针引线法

1.2 头插法

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def reverseBetween(self,head,left,right):
	# 设置dummyNode是这一类问题的一般做法
	dummy_node = ListNode(-1)# 创建一个虚拟节点
	dummy_node.next = head
	pre = deummy_node# 用于跟踪左边界之前的节点
	for _ in range(left -1):# _用于占位，该函数运行left-1次
		pre = pre.next# 定位到要移动区
	
	cur = pre.next# 取最近的一个开始交换
	for _ in range(right-left):
		next = cur.next
		cur.next = next.next
		next.next = pre.next
		pre.next = next
	return dummy_node.next	

1.3 穿针引线法

2.两两交换链表中的节点

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

方法一 递归

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */

var swapPairs = function(head) {
    if(head === null ||head.next ===null){
        return head
    }
    const newhead = head.next;
    head.next = swapPairs(newhead.next)//连接第一个和第三个
    newhead.next = head;//连接第二个和第一个
    return newhead
};

方法二 迭代

这里涉及到深浅拷贝问题

/*
@Date		:2023/11/12 21:50:47
@Author		:zono
@Description:链表设置
*/
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

// 创建链表节点
const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);

// 构建链表关系
node1.next = node2;
node2.next = node3;
node3.next = node4;

var swapPairs = function (head) {
  const dummyHead = new ListNode(0);
  dummyHead.next = head;
  let temp = dummyHead;//这里需要思考深浅拷贝
  while (temp.next !== null && temp.next.next !== null) {
    const node1 = temp.next;
    const node2 = temp.next.next;
    temp.next = node2;
    node1.next = node2.next;
    node2.next = node1;
    temp = node1;
  }
  return dummyHead.next;
};

function sort(currentNode) {
  while (currentNode !== null) {
    console.log(currentNode.val);
    currentNode = currentNode.next;
  }
}

sort(swapPairs(node1));

3.单链表加一

4.链表加法