LeetCode第24/25题:Swap Nodes in Pairs和Reverse Nodes in k-Group总结

题目一

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

× 大意: 给定一个链表,依次交换两个相邻节点,并返回头节点。
比如:
1->2->3->4 交换后应该为 2->1->4->3.

思路


比如我们的列表从A开始,先考虑一般情况:
我们想交换C和D。要交换C和D,我们需要将B.next指向D将C.next指向E,将D.next指向C,所以我们可以维护一个指针p进行从前往后的遍历,然后进行交换。一次交换需要涉及4个节点,所以每次交换我们又临时定义了p1,p2,p3。

  • 注意:
    1.因为我们交换的是p1和p2位置的节点,所以为了保证从前两个节点就开始交换,我们定义了一个哑节点O(代码中为header);
    2.当p1或者p2为空的时候,停止交换直接break,p3不用判断是否为空,因为用不到p3.next
    3.可能用不到三个辅助指针,但是这样思路不容易乱。

代码(python)

题目二

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

  • 大意: 升级上一道题,,,将交换两个点换成了没k个点反序一次。具体例子如上。

思路

交换过程中最少需要3个指针p1、p2和pre

代码(python)

发表评论

电子邮件地址不会被公开。 必填项已用*标注