专栏首页灰子学技术算法篇:链表之反转链表

算法篇:链表之反转链表

算法:

反转链表的基本操作可以拆分成下面四步:

1.保存前序节点,
2.保存后续节点,
3.当前节点指向前序节点
4.偏移前序节点和当前节点

其他的变形题目,主要围绕两个关键点:

1.反转之后的前序节点的处理
2.反转之后的后续节点的保存

题目1:反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

代码实现:

/*
解法:保存前序节点,
     保存后续节点,
     当前节点指向前序节点
     偏移前序节点和当前节点
     返回值 是前序节点
*/
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    curr := head
    for curr != nil {
        // fmt.Println(":",*curr)
        tmp := curr.Next
        curr.Next = pre
        pre = curr
        curr = tmp
    }
    return pre
}

执行结果:

题目2:

https://leetcode-cn.com/problems/reverse-linked-list-ii/

代码实现:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if head == nil || head.Next == nil || m == n{
        return head
    }
    first := head
    var begin *ListNode
    for i:= m; i>1; i-- { // 找到m节点的前序节点
        begin = first
        first = first.Next 
    }
    
    var h1 *ListNode = first
    for i:=n;i>m;i-- { // 找到第n个节点
        h1 = h1.Next   
    }
    var second *ListNode
    if h1.Next != nil { // 找到第n个节点的后续节点
        second = h1.Next
    }
    
    h1.Next = nil // 从n节点位置将链表分成两个单独的链表
   // first为反转后的前序节点,second为反转之后的后续节点,
   // 对于要反转的链表来说,second也是头节点的前序节点
    h1 = reverseList(first,second) 
    if begin != nil {
        begin.Next = h1
    } else {
        head = h1
    }
   
    return head
}
func reverseList(head *ListNode, last *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    curr := head
    var pre *ListNode = last
    for curr != nil { 
        tmp := curr.Next 
        curr.Next = pre
        pre = curr
        curr= tmp  
    }
    
    return pre
}
/*
解法:将需要反转的单独拉出一个列表来操作
然后,将前面的初始位置记录一下
将结尾位置作为反转之后的pre节点连接起来
备注:需要注意传入的起始和结束位置为整个链表的情况
*/

执行结果:

题目3:两两交换链表中的节点 https://leetcode-cn.com/problems/swap-nodes-in-pairs/submissions/

代码实现:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 // 解法:递归,1st和2nd节点反转,1st节点的next指向反转之后的链表,2nd.Next指向1st作反转处理
func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    // 两个临时节点定好位置
    first := head
    second:= head.Next
    // 反转处理
    first.Next = swapPairs(second.Next)
    second.Next = first
    return second
}

执行结果:

题目4:k个一组反转链表

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

代码实现:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 // 解法:递归,K个节点反转一次,然后头节点转换指向到下一个k链表,
 // 循环直到都操作结束
func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil {
        return head
    }
    begin,end := head,head
    for i:=0; i<k;i++{
        if end == nil { // 小于k的链表,直接返回
            return head
        }
        end = end.Next
    }
    // end表示的是反转之后的头节点,其实就是k链表之后的那个节点
    node := reverseList(begin,end)
    // 更换头节点的指向,方便下一次反转链表
    begin.Next = reverseKGroup(end,k)
    return node
}
// 一个链表的反转,node表示反转之后的头节点
func reverseList(head *ListNode, node *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    curr:= head
    pre := node
    for curr != node {
        tmp := curr.Next
        curr.Next=pre
        pre = curr
        curr= tmp
    }
    return pre
}

执行结果:

本文分享自微信公众号 - 灰子学技术(huizixueguoxue),作者:灰子学技术

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法篇:链表之删除链表中重复节点

    核心点在于如何找到重复节点,有序链表的话,只要下一个节点与当前节点数值一样就是重复节点,直接将当前节点指向下一个节点的下一个节点即可。

    灰子学技术
  • 算法篇:链表之倒数第k个节点

    该类型的题目,核心点在于如何找到倒数第k个节点的位置,典型的操作办法是,双指针的方法。

    灰子学技术
  • 算法篇:链表之删除和为0的元素

    利用前缀和的方法,例如前缀和[3,5,6,3,7],那么第一个3和最后一个3之间的节点之和就是0,不然的这两个数字不可能相等

    灰子学技术
  • 算法篇:链表之倒数第k个节点

    该类型的题目,核心点在于如何找到倒数第k个节点的位置,典型的操作办法是,双指针的方法。

    灰子学技术
  • 几种编程语言的优缺点

    我的旋风式简介会讲C、C++、Lisp、Java、Perl 、Ruby (我就是喜欢) 和 Python,把 Python 加进来是因为 —— 好吧,你看了就知...

    量化投资与机器学习微信公众号
  • 各种编程语言的优缺点

    文章转载自伯乐在线 原文地址:http://blog.jobbole.com/18587/ 【译注】:圣经记载:在远古的时候,人类都使用一种语言,全世界的人决定...

    智能算法
  • 亚马逊工程师论各种编程语言的优缺点

    我是攻城师
  • python3将变量写入SQL语句的实现方式

    以上这篇python3将变量写入SQL语句的实现方式就是小编分享给大家的全部内容了,希望能给大家一个参考。

    砸漏
  • Deep learning基于theano的keras学习笔记(1)-Sequential模型

    《统计学习方法》中指出,机器学习的三个要素是模型,策略和优算法,这当然也适用于深度学习,而我个人觉得keras训练也是基于这三个要素的,先建立深度模型,然后选用...

    李智
  • 使用变分递归神经网络通过主动推理对生灵特工进行目标导向的计划(CS AI)

    至关重要的是,要问代理人如何通过仅使用通过习惯的感觉运动体验获得的世界的部分模型来生成行动计划,从而实现目标。尽管许多现有的机器人技术研究都使用正向模型框架,但...

    刘子蔚

扫码关注云+社区

领取腾讯云代金券