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

示例 1：

输入：head = [1,2,3,4]

输出：[2,1,4,3]

示例 2：

输入：head = []

输出：[]

示例 3：

输入：head = [1]

输出：[1]

思路：

一、递归

1. 两两一组，head，nexthead，nexthead.next是下一对的开始

2. 返回新的头

时间复杂度，空间复杂度 O(N)

二、迭代

1.注意要循环调节要判断后面两个值都不为nil

2.创建一个亚节点

3.先连两边再连中间

时间复杂度O(N)，空间复杂度O(1)

二、实现方法

方法一：递归

1. 两两一组，head，nexthead，nexthead.next是下一对的开始

2. 返回新的头

时间复杂度，空间复杂度 O(N)


func swapPairs(head *ListNode) *ListNode{
    if head==nil||head.Next==nil{
        return head
    }
    newHead:=head.Next
    head.Next=swapPairs(newHead.Next)
    newHead.Next=head
    return newHead
}

方法二：迭代

1.注意要循环调节要判断后面两个值都不为nil

2.创建一个亚节点

3.先连两边再连中间

时间复杂度O(N)，空间复杂度O(1)


func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	dummy := &ListNode{}
	dummy.Next = head
	temp := dummy
	node1 := head
	for node1 != nil && node1.Next != nil {
		node2 := node1.Next
		temp.Next = node2
		node1.Next = node2.Next
		node2.Next = node1
		temp = node1
		node1 = temp.Next
	}
	return dummy.Next
}

三、可直接执行代码块


 
func main() {
	a := initNode(4, nil)
	b := initNode(3, a)
	c := initNode(2, b)
	//head:=initNode(1,c)
	PrintListNode(c)
	newHead := swapPairs(c)
	PrintListNode(newHead)
}
 
type ListNode struct {
	Val  int
	Next *ListNode
}
 
func initNode(val int, next *ListNode) *ListNode {
	return &ListNode{
		Val:  val,
		Next: next,
	}
}
 
func PrintListNode(node *ListNode) {
	for node != nil {
		fmt.Println(node.Val)
		node = node.Next
	}
}
 
// 递归法
/*func swapPairs(head *ListNode) *ListNode{
    if head==nil||head.Next==nil{
        return head
    }
    newHead:=head.Next
    head.Next=swapPairs(newHead.Next)
    newHead.Next=head
    return newHead
}
*/
 
// 迭代
func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	dummy := &ListNode{}
	dummy.Next = head
	temp := dummy
	node1 := head
	for node1 != nil && node1.Next != nil {
		node2 := node1.Next
		temp.Next = node2
		node1.Next = node2.Next
		node2.Next = node1
		temp = node1
		node1 = temp.Next
	}
	return dummy.Next
}

LeetCode206.反转链表| Easy

一、题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：

输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

二、实现方法

方法一：迭代

定义头结点为当前结点，

反转需要交换前要先记录下一个节点，为了反转后归位

时间复杂O(n)，空间复杂度O(1)


func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	cur:=head
	for cur!=nil{
		next:=cur.Next
		cur.Next=prev
		prev=cur
		cur=next
	}
	return prev
}

方法二：递归

   1. 确定终止条件，head!=nil一定能写出来；
   2. 递归公式：返回值为下一个节点
   3. 记录下一个位置（head.Next.Next，此时发现终止条件应该加一个head.Next!=nil），为了归位
   4. head.Next=nil，否则可能会产生环

时间复杂O(n)，空间复杂度O(n)


func reverseList2(head *ListNode) *ListNode {
	if head==nil || head.Next==nil {
		return nil
	}
	newNode:=reverseList2(head.Next)
	head.Next.Next=head
	head.Next=nil
	return newNode
}

三、可直接执行代码块


package main
 
import "fmt"
 
func main() {
	a:=initNode(1,nil)
	b:=initNode(2,a)
	c:=initNode(3,b)
	d:=initNode(4,c)
	head:=initNode(5,d)
	PrintListNode(head)
	reverseList2(head)
	fmt.Println("----------------------------")
	PrintListNode(a)
}
 
type ListNode struct {
	Val int
	Next *ListNode
}
 
func initNode(val int, next *ListNode) *ListNode {
	return &ListNode{
		Val: val,
		Next: next,
	}
}
 
func PrintListNode(node *ListNode){
	for node!=nil{
		fmt.Println(node.Val)
		node=node.Next
	}
}
 
// 迭代
// 反转需要交换前要先记录下一个节点，为了反转后归位
func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	cur:=head
	for cur!=nil{
		next:=cur.Next
		cur.Next=prev
		prev=cur
		cur=next
	}
	return prev
}
 
// 递归
/*	1. 确定终止条件，head!=nil一定能写出来；
	2. 递归公式：返回值为下一个节点
	3. 记录下一个位置（head.Next.Next，此时发现终止条件应该加一个head.Next!=nil），为了归位
	4. head.Next=nil，否则可能会产生环*/
func reverseList2(head *ListNode) *ListNode {
	if head==nil || head.Next==nil {
		return nil
	}
	newNode:=reverseList2(head.Next)
	head.Next.Next=head
	head.Next=nil
	return newNode
}

持续更新...

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/程序诗人/article/detail/61253