单向链表反转 2022-02-22 周二

基本思路

• 准备1：判空，head为空（无节点），直接返回空指针；

• 准备2：Head为输入指针，最好不要修改它，所以用一个指针，current代替它

• 准备3：两个辅助节点：previous（反转后的新head），next（暂存下一个节点）

• 准备4：结束条件current 为空，这个时候，previous就是反转后的头节点，返回就好。

• 步骤1：保存next指针
  next = current.next;

• 步骤2：反转
  current.next = previous;

• 步骤3：移动到下一个
  previous = current;
  current = next;

• 返回：previous

C代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head) {
    // 判空
    if (head == NULL) {
        return NULL;
    }

    // 三个指针
    struct ListNode *current = head;
    struct ListNode *previous = NULL;
    struct ListNode *next = NULL;
    
    // 反转
    while(current != NULL) {
        next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    
    // 返回反转后的新头
    return previous;
}

JS代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // 判空
    if (!head) {
        return null;
    }

    // 三个指针
    let previous = null;
    let current = head;
    let next = null;

    // 反转
    while (current) {
    // 保存next
    next = current.next;
    // 替换next
    current.next = previous;
    // 设置pre的值
    previous = current;
    // 设置当前项的值
    current = next;
    }
      
    return previous;
};

Swift代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        // 判空
        if head == nil {
            return nil
        }

        // 三个指针
        var current = head
        var previous : ListNode? = nil
        var next : ListNode? = nil

        // 反转
        while current != nil {
            next = current?.next
            current?.next = previous
            previous = current
            current = next
        }

        // 返回新的head
        return previous
    }
}

简单比较

• swift和JavaScript的代码真的很像

• 语法上JavaScript随意一些，当然代码安全差距很大（编译语言和脚本语言）

• 性能上C > Swift > JavaScript

性能差距

参考文章

看一遍就理解，图解单链表反转

C代码

JS代码

Swift代码