胡桃仁

虚度光阴27 载

最近刷链表的题,记录一下用到双指针解决的题目,复习一下,思路还是那个思路,为了求快,用php 重写一遍这几个。
(这几个几乎都要用到虚节点,基操,感觉链表题都可以尝试创建个虚节点促使自己找到思路。)

链表类

1
2
3
4
5
6
7
8
9
10
11
<?php

class ListNode{
public $val;
public $next;

public function __construct($val)
{
$this->val = $val;
}
}

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

描述

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

示例:

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

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

说明:

给定的 n 保证是有效的。

题解

没啥好说的,快慢指针,快指针节点进n 步,然后同时步进,直到快指针指向null。删除慢指针指向的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function removeNthFromEnd($head, $n): ListNode
{
$preprev = new ListNode(-1);
$preprev->next = $head;
$quick = $preprev;
$slow = $preprev;

while ($n > 0) {
$quick = $quick->next;
$n--;
}

while ($quick->next != null) {
$quick = $quick->next;
$slow = $slow->next;
}

$slow->next = $slow->next->next;
return $preprev->next;
}

21. 合并两个有序链表

描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

1
2
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

题解

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
function mergeTwoLists($l1, $l2) :ListNode {
if ($l1 == null) {
return $l2;
}
if ($l2 == null) {
return $l1;
}

$preprev = new ListNode(-1);
$pre = $preprev;
while ($l1 != null || $l2 != null) {
if ($l1 == null) {
$pre->next = $l2;
break;
}
if ($l2 == null) {
$pre->next = $l1;
break;
}
if ($l1->val < $l2->val) {
$pre->next = $l1;
$l1 = $l1->next;
} else {
$pre->next = $l2;
$l2 = $l2->next;
}
$pre = $pre->next;
}
return $preprev->next;
}

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

描述

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例:

1
给定 1->2->3->4, 你应该返回 2->1->4->3.

题解

虚节点每次进两步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function swapPairs($head) {
$preprev = new ListNode(-1);
$preprev->next = $head;
$pre = $preprev;
while ($pre->next != null && $pre->next->next != null) {

$slow = $pre->next;
$quick = $pre->next->next;

$pre->next = $quick;
$slow->next = $quick->next;
$quick->next = $slow;
$pre = $slow;
}
return $preprev->next;
}

评论