leetcode:反转链表

反转链表I

题目

  • 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
// Definition for singly-linked list.
 public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
 }
  • 示例:
    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL
  • 限制:
    0 <= 节点个数 <= 5000

题解

class Solution {
    public ListNode reverseList(ListNode head) {
    	//链表为null直接返回
        if(head == null){
            return null;
        }
        //第一个节点指向head
        ListNode prev = head;
        //当前节点指向下个节点
        ListNode current = head.next;
        prev.next = null;
        //当前节点为null,则到了末尾,跳出
        while(current!=null){
        	//以下四步为节点替换
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
}

反转链表II

题目

  • 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表。
  • 示例 1:
    输入:head = [1,2,3,4,5], left = 2, right = 4
    输出:[1,4,3,2,5]
  • 示例 2:
    输入:head = [5], left = 1, right = 1
    输出:[5]
//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; }
 }

题解

在这里插入图片描述

  1. 第一步:
    在这里插入图片描述
ListNode dummy = new ListNode(-1);
        dummy.next = head;
        head = dummy;
        //找出要反转的起始节点的前一个节点
        for(int i=1;i<m;i++){
            head = head.next;
        }
        ListNode prevM = head;
        ListNode mNode = head.next;
        ListNode nNode = mNode;
        ListNode postN = nNode.next;
  1. 第二步:
    在这里插入图片描述
for(int i=m;i<n;i++){
            ListNode next = postN.next;
            postN.next = nNode;
            nNode = postN;
            postN = next;
        }
  1. 第三步:
    在这里插入图片描述
  2. 第四步
    在这里插入图片描述
    可以看到链表已经反转了:
    在这里插入图片描述

代码

public static ListNode reverseBetween(ListNode head, int m, int n) {
        //链表为null直接返回
        if(head == null && m>=n){
            return null;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        head = dummy;
        for(int i=1;i<m;i++){
            head = head.next;
        }
        ListNode prevM = head;
        ListNode mNode = head.next;
        ListNode nNode = mNode;
        ListNode postN = nNode.next;
        for(int i=m;i<n;i++){
            ListNode next = postN.next;
            postN.next = nNode;
            nNode = postN;
            postN = next;
        }
        prevM.next = nNode;
        mNode.next = postN;
        return dummy.next;
    }

版权声明:本文为nianqrzhanghw原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。