算法通关村第二关——终于学会链表反转了-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法通关村第二关——终于学会链表反转了。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

算法通关村第二关——终于学会链表反转了,链表,数据结构

方法一：建立虚拟头结点辅助反转

创建一个虚拟头节点，获取链表中每个节点，用虚拟头节点指向这个节点，并在链表中删除，

算法通关村第二关——终于学会链表反转了,链表,数据结构

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
       ListNode ans = new ListNode(-1);
       ListNode cur = head;
       while(cur != null){
           ListNode next = cur.next;
           cur.next = ans.next;
           ans.next = cur;
           cur = next;
       }
       return ans.next;
    }
}

方法二：直接操作链表实现反转

记录当前节点(cur),前驱节点(pre),后继节点(next),先将当前节点的下一个节点指向前驱节点，然后将当前节点赋给前驱节点，后继节点赋给当前节点

算法通关村第二关——终于学会链表反转了,链表,数据结构

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
       ListNode pre = null; 
       ListNode cur = head;
       while(cur != null){
           ListNode next = cur.next;
           cur.next = pre;
           pre = cur;
           cur = next;
       }
       return pre;
    }
}

方法三：递归文章来源地址https://www.toymoban.com/news/detail-633810.html

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
      if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

到了这里，关于算法通关村第二关——终于学会链表反转了的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！