讨论/《链表》 - 反转链表/
《链表》 - 反转链表
共 27 个回复
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 想象递归已经层层返回,到了最后一步
        // 以链表 1->2->3->4->5 为例,现在链表变成了 5->4->3->2->null,1->2->null(是一个链表,不是两个链表)
        // 此时 newHead是5,head是1
        ListNode newHead = reverseList(head.next);
        // 最后的操作是把链表 1->2->null 变成 2->1->null
        // head是1,head.next是2,head.next.next = head 就是2指向1,此时链表为 2->1->2
        head.next.next = head;
        // 防止链表循环,1指向null,此时链表为 2->1->null,整个链表为 5->4->3->2->1->null
        head.next = null;
        return newHead;
    }
}
6
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}
5

C++版本,p1,p2,p3三个指针实现翻转

vector<int> reversePrint(ListNode* head) {
vector<int> temp;

    ListNode* p1 = new ListNode;
    ListNode* p2 = new ListNode;
    ListNode* p3 = new ListNode;
    p1 = NULL;
    p2 = head;
    while(p2!=NULL)
    {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }

    while(p1!=NULL)
    {
        temp.push_back(p1->val);
        p1 = p1->next;
    }
    return temp;
}
2

简单一哥题解
1.遍历head,然后用一个temp来记录上一个head节点.
2.然后用result第二个链表进行头插法,插入temp,一直到head为空为止(head为空temp,就是最后一个元素)

class Solution {
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode result = null;
        ListNode temp = null;
        while (head != null) {
            //temp用来记录head前一个元素
            temp = head;
            head = temp.next;
            temp.next = result;
            //result为第二个节点的头节点
            result = temp;
        }
        return result;
    }
}

a1b4ec2c830f16069e2a9d17f8ac4cc.png

1

JavaScript版本~

创建一个假头,将新的节点不断插入到假头的后一个节点,感觉相对好理解一点

var reverseList = function (head) {
    const dummy = new ListNode()
    let cur = head
    while (head) {
        cur = head
        head = head.next
        cur.next = dummy.next
        dummy.next = cur
    }
    return dummy.next
};

递归版本

var reverseList = function (head) {
    if (!head) return head
    const dummy = new ListNode()
    dummy.next = head
    let cur = dummy
    //用于递归的方法
    const dfs = (node) => {
        if (node && !node.next) return node //退出条件
        let newNode = dfs(node.next)
        cur.next = newNode
        newNode.next = null
        cur = cur.next
        return node
    }
    dfs(dummy)
    return dummy.next
};
1

遍历并指向前一个
image.png

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr)   return head;
        ListNode *pre = head;
        ListNode *ptr = head->next;
        head->next = nullptr;
        while(ptr!=nullptr)
        {
            ListNode *tmp = ptr->next;
            ptr->next = pre;
            pre = ptr;
            ptr = tmp;
        }
        head = pre;
        return head;
    }
};
1

双指针 + 递归

1
func reverseList(head *ListNode) *ListNode {
    return process(nil, head)
}
func process (pre,cur *ListNode) *ListNode {
    // base case
    // 1 -> 2 -> nil
    // 1 <- 2 <- nil
    //     pre   cur
    if cur == nil  {
        return pre
    }
    // 待处理的后半段
    waitProcess := cur.Next
    // 当前指针指向前一个节点
    cur.Next = pre
    // 去处理剩下的部分
    return process(cur,waitProcess)
}
1

newHead用来记录反转后的新头节点,在递归中newHead的值不会改变,一直是原链表的最后一个节点。递归代码也可以这样写

class Solution {
    private ListNode newHead;

    public ListNode reverseList(ListNode head) {
        reverse(head);
        return newHead;
    }

    private void reverse(ListNode head) {
        if (head == null || head.next == null) {
            newHead = head;
            return;
        }
        reverse(head.next);
        head.next.next = head;
        head.next = null;
    }
}
1

又是一道二刷的题目,这次得比上次简练些许:

 public ListNode reverseList(ListNode head) {
        //排除空链特殊情况
        if(head==null)return null;
        //指针h指向反转后链表链首 指针p指向待翻转的节点
        ListNode h=head,p=head.next;
        while (p!=null) {
            //注意指针head指向翻转段的最后一个节点
            head.next=p.next;
            p.next=h;
            h=p;
            p=head.next;
        }
        return h;
    }