[数据结构与算法]leetcode算法入门系列学习10(递归 / 回溯)『 合并两个有序链表 | 反转链表』

【= 合并两个有序链表 =】

题目描述

传送门

解题思路

递归排序插入

解题方法

• PHP

function mergeTwoLists($l1, $l2) {
   if($l1 == null) {
        return $l2;
    }else if($l2 == null) {
        return $l1;
    } else if($l1->val <= $l2->val) {
        $l1->next = $this->mergeTwoLists($l1->next, $l2);
        return $l1;
    } else {
        $l2->next = $this->mergeTwoLists($l1, $l2->next);
        return $l2;
    }
}

• GO

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    } else if l2 == nil {
        return l1
    } else if l1.Val <= l2.Val {
        l1.Next = mergeTwoLists(l1.Next, l2)
        return l1
    } else {
        l2.Next = mergeTwoLists(l1, l2.Next)
        return l2
    }
}

【= 反转链表 =】

题目描述

传送门

解题思路

迭代指针的方式理解起来有点绕，大家可以仔细学习理解一下🤔🤔🤔
1、单链表为空则直接返回
2、定义两个节点，prev(前一个节点)，cur(当前节点)
3、遍历链表：每次让前一个节点next(prev.next)指向当前节点curr 实现局部反转 同时prev、curr 向前移动一个位置
4、循环直至pre到达聊表尾部

解题方法

• PHP

 function reverseList($head) {
    $pre = null;
    $cur = $head;
    while($cur) {
        // 获取当前节点的next
        $next = $cur->next;
        // 交换prev与curr指针
        $cur->next = $pre;
        $pre = $cur;
        // 指针后移
        $cur = $next;
    }
    return $pre;
}

• GO

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