当前位置: 首页 > 游戏攻略 > 使用Golang解决链表问题:交换相邻节点

使用Golang解决链表问题:交换相邻节点

来源:网络 作者:趣玩小编 发布时间:2024-04-19 08:50:14

最近我一直在使用Golang来解决算法问题,因为它更接近通用算法,没有像动态脚本语言那样的语法糖,能够真正依靠实力解决问题。
下面这道题很有趣,也是一道链表题目,具体如下:

这是一道链表问题:交换相邻节点。给定一个链表,交换每两个相邻的节点并返回其头节点。在解决问题时,不能修改链表节点的值(即只能修改节点本身)。

24. Swap Nodes in Pairs
Solved
Medium
Topics
Companies
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)
 

Example 1:


Input: head = [1,2,3,4]
Output: [2,1,4,3]
Example 2:

Input: head = []
Output: []
Example 3:

Input: head = [1]
Output: [1]
 

Constraints:

The number of nodes in the list is in the range [0, 100].
0 <= Node.val <= 100

快速思考了一下,想到这个交换节点的事儿可以用递归去实现,通过三个指针prev, current, next不断移动,实现相邻节点交换,代码如下:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
	
	if head == nil || head.Next == nil {
		return head
	}
	
	if head.Next.Next == nil {
		next := head.Next
		head.Next = nil
		next.Next = head
        head = next

		return head
	}

	prev, cur, nxt := head, head.Next, head.Next.Next
    cur.Next = prev
    head = cur
	prev.Next = swapPairs(nxt)

    return head
}

递归虽然好,但是也会有一些性能上的担忧,毕竟递归调用太深,可能会引发堆栈溢出。后面再仔细推敲了一下,完全可以用2个指针不断进行交换,可以不用递归。这里还是要用一个dump节点来方便的保存修改后的链表,具体如下:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
	
	dump := &ListNode{Val: 0}
	dump.Next = head
	prevNode := dump
	currentNode := head

    for currentNode != nil && currentNode.Next != nil {
		prevNode.Next = currentNode.Next
		currentNode.Next = currentNode.Next.Next
		prevNode.Next.Next = currentNode
		prevNode = currentNode
		currentNode = currentNode.Next
	}

	return dump.Next
}

最终它们的时间复杂度是O(N),空间复杂度O(1),都非常棒。如果是你,你更喜欢哪种解法呢?欢迎在评论区留言交流。

相关攻略
热门推荐 更多 +
休闲益智 | 945.71MB
我的世界是一款风靡全球的3D第一人称沙盒...
9.6
角色扮演 | 878.96MB
最新版《汉家江湖》是一款以武侠为题材、以...
9.5
飞行射击 | 262.79MB
《荒野乱斗》是快节奏射击类多人对战游戏。...
9.5
飞行射击 | 102.9M
掌上飞车手游app是由腾讯特别为QQ飞车...
9.2
休闲益智 | 263.56MB
开心消消乐是一款轻松休闲的手游,也是一款...
9.6