反转链表的几种模式

​链表作为一种常用的数据结构,面试当然也是家常便饭。此处就来谈谈关于链表面试中的的几种常见反转。

1.逆序所有节点

输入:list = 1->2->3->4->5->null
输出:list = 5->4->3->2->1->null

思路:定义previous、current、next(即前驱、当前、后继)指针。从头结点开始往后一个个逆序,即不断让current.next = previous即可。

JAVA参考代码

public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}
public ListNode reverse(ListNode current) {
    ListNode previous = null; //前驱结点
    while (current != null) {
        //next记录下一个节点,current是当前节点
        ListNode next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

2.逆序第m到n个节点(1 ≤ m ≤ n ≤ size)

输入: list = 1->2->3->4->5->6->null, m = 2 and n = 5,
输出: list = 1->5->4->3->2->6->null

思路:找出原链表中第m到n个元素,进行逆序后。再接回原来的链表中。

  • a.找出原链表中m的前一个结点mPrevNode;
  • b.取出原链表第m到n个元素,进行逆序;
  • c.记录原链表中n的下一个结点nNextNode;
  • d.原链表结点mPrevNode指向逆序后的头结点;
  • e.逆序后的尾结点指向原链表结点nNextNode。

JAVA参考代码

public ListNode reverse4Range(ListNode head, int m, int n) {
    if (m >= n || head == null) {
        return head;
    }

    ListNode newList = new ListNode(0);
    newList.next = head;
    head = newList;

    for (int i = 1; i < m; i++) {
        if (head == null) {
            return null;
        }
        head = head.next;
    }

    ListNode mPreNode = head;
    ListNode mNode = head.next;
    ListNode nNode = mNode, nNextNode = mNode.next;
    for (int i = m; i < n; i++) {
        if (nNextNode == null) {
            return null;
        }
        ListNode temp = nNextNode.next;
        nNextNode.next = nNode;
        nNode = nNextNode;
        nNextNode = temp;
    }
    mNode.next = nNextNode;
    mPreNode.next = nNode;

    return newList.next;
}

3.按K个值分组逆序

即从头结点开始每k个逆序,若小于k个则不做处理。
输入:list = 1->2->3->4->5->null, k=3
输出:list = 3->2->1->4->5->null

思路:顺序按k个一组执行逆序

  • a.记录前一个k组逆序的尾结点 prevTail;
  • b.记录下一组的头结点 nextGroupHead;
  • c.找到k个结点则进行该组逆序, 若不足k个则直接指向后结点;
  • d.前一个尾结点 prevTail 指向逆序后的头结点 reverseHead。

JAVA参考代码

public ListNode reverse4KGroup(ListNode head, int k) {
    ListNode newList = new ListNode(0);
    ListNode prevTail = newList;
    ListNode nextGroupHead = head;
    while (head != null) {
        for (int i = 0; i < k-1 && head != null; i++) {
            head = head.next;
        }

        if (head != null) {
            ListNode nextHead = head.next;
            head.next = null;
            ListNode reverseHead = reverse(nextGroupHead); // 题1中的reverse()
            prevTail.next = reverseHead;
            prevTail = nextGroupHead;
            nextGroupHead = nextHead;
            head = nextGroupHead;
        } else {
            prevTail.next = nextGroupHead;
        }
    }
    return newList.next;
}

public ListNode reverse(ListNode current) {
    ListNode previous = null; //前驱结点
    while (current != null) {
        //next记录下一个节点,current是当前节点
        ListNode next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    return previous;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 过程 迭代过程中需要三个指针: p用来指向当前待处理的结点 lastp 指向上一个处理完的结点,初始为空。这样的话...
    熊白白阅读 403评论 0 0
  • LeetCode-链表 链表(Linked List)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺...
    raincoffee阅读 1,268评论 0 6
  • 删除链表的倒数第N个节点 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例:给定一个链表:...
    我是小曼巴阅读 332评论 0 0
  • 题目汇总https://leetcode-cn.com/tag/linked-list/剑指 Offer 18. ...
    今天柚稚了么阅读 312评论 0 0
  • 题目汇总https://leetcode-cn.com/tag/linked-list/2. 两数相加中等19. ...
    今天柚稚了么阅读 193评论 0 0