反转部分单向链表_

pein531

找到开始反转的子链表头节点，然后开始常规的反转操作即可

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] list = br.readLine().trim().split(" ");
        ListNode head = new ListNode(Integer.parseInt(list[0]));
        ListNode cur = head;
        for(int i = 1; i < n; i++){
            cur.next = new ListNode(Integer.parseInt(list[i]));
            cur = cur.next;
        }
        String[] params = br.readLine().split(" ");
        int start = Integer.parseInt(params[0]);
        int end = Integer.parseInt(params[1]);
        head = reversePartLinkedList(head, start, end);
        while(head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
    
    private static ListNode reversePartLinkedList(ListNode head, int start, int end) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        for(int i = 1; i < start; i++)
            prev = prev.next;
        ListNode cur = prev.next;       // 开始翻转的链表头结点
        for(int i = start; i < end; i++){
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
        return dummy.next;
    }
}

发表于 2021-06-06 20:13:53 回复(0)

C/C++

三十不惑mm

list_node * reverse_list(list_node * head, int L, int R)
{
//////在下面完成代码
list_node* pStartnode = head;
list_node* pStartPrenode = nullptr;
list_node* pEndnode = head;
list_node* pEndNextnode;
for(int i=0;i<L-1;i++){
pStartPrenode = pStartnode;
pStartnode = pStartnode->next;
}
for(int i=0;i<R-1;i++){
pEndnode = pEndnode->next;

}
pEndNextnode = pEndnode->next;
list_node* pCurrnode = pStartnode;
list_node* pPrenode = nullptr;
list_node* pNextnode = nullptr;
while(pCurrnode->next!=pEndNextnode){
pNextnode = pCurrnode->next;
pCurrnode->next = pPrenode;
pPrenode = pCurrnode;
pCurrnode = pNextnode;
}
pCurrnode->next = pPrenode;


pStartnode->next = pEndNextnode;
if(pStartPrenode!=nullptr){
pStartPrenode->next = pCurrnode;
return head;
}else{
return pCurrnode;
}

}

发表于 2020-07-23 20:06:10 回复(0)

唉梅子

list_node * reverse_list(list_node * head, int L, int R)
{
    //////在下面完成代码
    if(head == nullptr || R < L || L < 1)
        return head;
    list_node * p = head;
    list_node * pre = nullptr;//
    list_node * pos = nullptr;
    int len = 0;
    while(p){
        len++;
        pre = (len == L -1 ? p : pre);
        pos = (len == R + 1 ? p : pos);
        p = p->next;
    }
    if(R > len)
        return head;
    list_node *node1 = (pre == nullptr ? head : pre->next);
    list_node *node2 = node1->next;
    node1->next = pos;
    list_node *next = nullptr;
    while(node2 != pos){
        next = node2->next;
        node2->next = node1;
        node1 = node2;
        node2 = next;
    }
    if(pre != nullptr){
        pre->next = node1;
        return head;
    }
    return node1;
}

发表于 2019-08-02 20:15:12 回复(0)

C/C++

nbgao

list_node * reverse_list2(list_node *head, list_node *end, int l){
    list_node *pre = end, *p = head, *q = head->next;
    while(l--){
        p->next = pre;
        pre = p;
        p = q;
        q = p->next;
    }
    return pre;
}

list_node * reverse_list(list_node * head, int L, int R)
{
    list_node * rhead = new list_node();
    rhead->next = head;
    list_node *p = rhead;
    for(int i=0;i<L-1;i++)
        p = p->next;
    list_node *q = p->next;
    for(int i=L;i<R+1;i++)
        q = q->next;
    p->next = reverse_list2(p->next, q, R-L+1);
    return rhead->next;
}

发表于 2020-04-29 01:05:26 回复(0)

Java

给我一个面试吧

class ListNode{
    public int val;
    public ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int length = scanner.nextInt();
        int[] val = new int[length];
        for (int i = 0; i < length; i++) {
            val[i] = scanner.nextInt();
        }
        int left = scanner.nextInt();
        int right = scanner.nextInt();
        ListNode head = new ListNode(val[0]);
        ListNode cur = head;
        for (int i = 1; i < length; i++) {
            cur.next = new ListNode(val[i]);
            cur = cur.next;
        }
        head = reversePartLinkedList(head,left,right);
        while (head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    private static ListNode reversePartLinkedList(ListNode head, int start, int end) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;

        for (int i = 1;i < start;i++){
            prev = prev.next;
        }
        ListNode prev2 = prev.next;
        ListNode prev3 = prev.next;
        ListNode cur = prev2.next;
        for (int i = start; i < end; i++) {
            ListNode curNext = cur.next;
            cur.next = prev2;
            prev2 = cur;
            cur = curNext;
            prev3.next = curNext;
        }
        prev.next = prev2;
        return dummy.next;
    }
}

发表于 2023-04-19 22:06:02 回复(0)

被发好人卡的奇亚籽很想回家

发表于 2023-11-24 13:05:53 回复(0)

Java

求求一个大厂offer

import java.util.Scanner;

/*
 * 反转部分单向链表
 */
class Node {
    int val;
    Node next;
    public Node(int val) {//构造方法
        super();
        this.val = val;
        this.next = null;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int []value = new int[len];

        for (int i = 0; i < len; i++) {
            value[i] = sc.nextInt();
        }

        int left = sc.nextInt();
        int right = sc.nextInt();

        reverse( value, left-1, right-1);
        Node head = arrayToList(value);
        Node node;
        for (node = head; node.next != null; node = node.next) {
            System.out.print(node.val + " ");
        }
        System.out.print(node.val);
    }
    public static void reverse(int []value, int left, int right) {
        while (left < right) {
            int tmp = value[left];
            value[left] = value[right];
            value[right] = tmp;
            left++;
            right--;
        }
    }
    public static Node arrayToList(int []value) {
        Node head = new Node(-1);
        Node node = head;
        for (int i = 0; i < value.length; i++) {
            Node newNode = new Node(value[i]);
            node.next = newNode;
            node = newNode;
        }
        return head.next;
    }
}

发表于 2023-04-09 17:50:15 回复(0)

侬是一个好人

import java.util.*;
import java.io.*;

class ListNode{
    public int val;
    public ListNode next;
    public ListNode(int val){
        this.val = val;
        this.next = null;
    }
}


public class Main{
    
    public static ListNode ReverseList(ListNode Head,int L,int R){
        ListNode pHead = new ListNode(-1);
        pHead.next = Head;
        ListNode prevNode = pHead;
        for(int i = 0; i < L-1; i++){
            prevNode = prevNode.next;
        }
        ListNode cur = prevNode.next;
        for(int i = 0; i < R-L; i++){
            //先保存cur的下一个结点
            ListNode curNext = cur.next;
            //删除下一个结点，cur指向curNext的下一个结点
            cur.next = curNext.next;
            //删除的结点头插到prevNode的后面
            curNext.next = prevNode.next;
            prevNode.next = curNext;
        }
        ListNode list = pHead.next;
        return list;
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while((str = reader.readLine()) != null){
            int n = Integer.parseInt(str);
            str = reader.readLine();
            String[] list = str.trim().split(" ");
            ListNode head = new ListNode(Integer.parseInt(list[0]));
            ListNode cur = head;
            for(int i = 1; i < n; i++){
                cur.next = new ListNode(Integer.parseInt(list[i]));
                cur = cur.next;
            }
            str = reader.readLine();
            String[] params = str.trim().split(" ");
            int L = Integer.parseInt(params[0]);
            int R = Integer.parseInt(params[1]);
            ListNode Head = ReverseList(head,L,R);
            while(Head != null){
                System.out.print(Head.val + " ");
                Head = Head.next;
            }
        }
    }
}

发表于 2023-02-10 16:39:04 回复(0)

Java

two倩

import java.util.*;
class ListNode{
int val;
ListNode next;

public ListNode(int val) {
this.val = val;
}
}
public class Main {
static Scanner scanner = new Scanner(System.in);

public static void main(String[] args) {
int n = scanner.nextInt();
ListNode head = create(n);
int left = scanner.nextInt();
int right = scanner.nextInt();
head = partReserve(head, left, right);
print(head);
}
private static void print(ListNode head){
while(head!=null){
System.out.print(head.val+" ");
head=head.next;
}
}
private static ListNode partReserve(ListNode head,int left,int right) {
if (head == null || left == right)
return head;
//start指向left结点的前驱结点
ListNode ph = new ListNode(-1);
ph.next = head;
ListNode start = ph;
int x=left;
while (x-- > 1)
start = start.next;

ListNode cur = start.next;
ListNode phead = cur;
//cur 指向第left个结点
ListNode curnext = cur.next;

while (curnext != null && left < right) {
ListNode tmp = curnext.next;
curnext.next = cur;
cur = curnext;
curnext = tmp;
left++;
}
start.next = cur;
phead.next = curnext;
return ph.next;
}
private static ListNode create(int n) {
ListNode head = new ListNode(0);
ListNode cur = head;
while (n-- > 0) {
cur.next = new ListNode(scanner.nextInt());
cur = cur.next;
}
return head.next;
}
}

发表于 2022-09-09 14:04:01 回复(0)

爱干饭的猿

找到指定部分节点（left - right），然后进行反转。详见代码

import java.util.Scanner;

/**
 * 反转部分单向链表
 * @author haomin
 * @date 2022/05/26 18:51
 **/
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        Node head = new Node(-1);
        Node cur = head;
        // 1. 得到题给的链表
        for (int i = 0; i < num; i++) {
            Node node = new Node(in.nextInt());
            cur.next = node;
            cur = cur.next;
        }

        int leftIndex = in.nextInt();
        int rightIndex = in.nextInt();

        // 2. 记录left左边第一个节点
        Node frontNode = head;
        // 3. 记录right右边第一个节点
        Node hinderNode = head;

        // 2.1
        for (int i = 0; i < leftIndex-1; i++) {
            frontNode = frontNode.next;
        }
        // 得到开始进行反转的节点
        Node firstNode = frontNode.next;

        // 3.1
        for (int i = 0; i <= rightIndex; i++) {
            hinderNode = hinderNode.next;
        }

        // 4. 反转指定部分链表
        // 连接right后面的节点
        Node newNode = hinderNode;
        int count = rightIndex - leftIndex + 1;
        while (count-- != 0){
            Node pre = new Node(firstNode.val);
            pre.next = newNode;
            newNode = pre;

            firstNode = firstNode.next;
        }
        // 连接left前面的节点
        frontNode.next = newNode;

        // 5. 打印
        head = head.next;
        while (head != null){
            System.out.print(head.val+" ");
            head = head.next;
        }
    }
}

class Node{
    int val;
    Node next;

    public Node(int val) {
        this.val = val;
    }
}

发表于 2022-05-26 19:55:02 回复(0)

Relili

今天不吃了

let n=parseInt(readline())
let nums=readline().split(' ').map(item=>parseInt(item))
let [L,R]=readline().split(' ').map(item=>parseInt(item))

const listNode=function(val){
    this.val=val
    this.next=null
}

const head=new listNode(-1)
let p=head
for(let i=0;i<n;i++){
    const node=new listNode(nums[i])
    p.next=node
    p=node
}
let q=head
let pre=null,last=null
p=head.next
let count=R-L
let flag=0
while(L!=0||R!=0){
    L--
    R--
    if(L==0){
        pre=q
        flag++
    }
    if(R==0){
        last=p
        flag++
    }
   if(flag==2) break
   q=q.next
   p=p.next
   if(p==null) break
}
if(p==null){
    last=q
}
while(pre.next!=last){
    let cur=pre.next
    pre.next=cur.next
    cur.next=last.next
    last.next=cur
}
p=head.next
let res=[]
while(p){
    res.push(p.val)
    p=p.next
}
console.log(res.join(' '))

发表于 2021-07-01 14:31:18 回复(0)

跳动の字节

# include <bits/stdc++.h>
using namespace std;

struct list_node{
int val;
struct list_node * next;
};

list_node * input_list(void)
{
int n, val;
list_node * phead = new list_node();
list_node * cur_pnode = phead;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &val);
if (i == 1) {
cur_pnode->val = val;
cur_pnode->next = NULL;
}
else {
list_node * new_pnode = new list_node();
new_pnode->val = val;
new_pnode->next = NULL;
cur_pnode->next = new_pnode;
cur_pnode = new_pnode;
}
}
return phead;
}

list_node * reverse_list(list_node * head, int L, int R)
{
//////在下面完成代码
list_node whead;
whead.next = head;
list_node *pre = &whead, *p = head, *to = p->next;
int t = 1;
while(t < L){
pre = p;
p = to;
to = to->next;
++t;
}
list_node *stopb = pre, *stopc = p;
pre = nullptr;

while( t <= R && p) {
p->next = pre;
pre = p;
p = to;
to = to->next;
t++;
}
stopb->next = pre;
stopc->next = p;
return whead.next;

}

void print_list(list_node * head)
{
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
puts("");
}

int main ()
{
int L, R;
list_node * head = input_list();
scanf("%d%d", &L, &R);
list_node * new_head = reverse_list(head, L, R);
print_list(new_head);
return 0;
}

发表于 2021-06-19 10:45:15 回复(0)

Python

毓毓子最可爱

n=int(input())
number_list=list(map(int,input().split()))
l,r=map(int,input().split())
#截取要反转的部分
temp_list=number_list[l-1:r]
temp_list.reverse()
ans=number_list[0:l-1]+temp_list+number_list[r:]
print(" ".join(map(str,ans)))

发表于 2021-06-17 20:04:01 回复(0)

蜗壳☁️

import java.util.*;
import java.io.*;
class Node{
    int val;
    Node next;
    public Node(int val){
        this.val = val;
    }
}
public class Main{
    private static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    private static int nextInt(){
        try{
            st.nextToken();
            return (int) st.nval;
        } catch(Exception e){
            throw new RuntimeException(e);
        }
    }
    public static Node build(int n){
        Node dummy = new Node(-1);
        Node cur = dummy;
        for(int i = 0; i < n; i++){
            Node temp = new Node(nextInt());
            cur.next = temp;
            cur = cur.next;
        }
        return dummy.next;
    }
    public static Node partReverse(Node head, int left, int right){
        Node dummy = new Node(-1);
        dummy.next = head;
        Node pre = dummy;
        for(int i = 1; i < left; i++)
            pre = pre.next;
        head = pre.next;
        for(int i = left; i < right; i++){
            Node nextNode = head.next;
            head.next = nextNode.next;
            nextNode.next = pre.next;
            pre.next = nextNode;
        }
        return dummy.next;
    }
    public static void main(String[] args){
        int n = nextInt();
        Node head = build(n);
        int start = nextInt();
        int end = nextInt();
        head = partReverse(head, start, end);
        StringBuilder res = new StringBuilder();
        while(head != null){
            res.append(head.val).append(" ");
            head = head.next;
        }
        System.out.println(res.toString().trim());
    }
}

发表于 2021-04-10 16:04:14 回复(0)

hanchuanlin

list_node * reverse_list(list_node * head, int L, int R)
{
    //////在下面完成代码
    list_node *pre,*cur,*tail,*hs,*t;
    pre = t = hs = head;
    if(head->next == NULL) return head;
    for(int i = 1; i < R; i++){
        if(i < L){
            if(i == L-1){  
                hs = pre;//hs为L的前一个节点
                t = pre->next;//t为第L个节点
            }
            pre = pre->next;
        }
        else{
            if(i == L) cur = pre->next;
            tail = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tail;
        }
    }
    // 如果L=1（此时t == head），第pre个节点就成了第一个节点否则head为第一个节点
    // 也可以创造一个头结点，然后再进行反转，这样就无需考虑L的情况。
    // 例如
    //    反转1到3，1 2 3 4 5，pre=3成了第一个节点
    //    反转2到4，1 2 3 4 5变成了1 4 3 2 5，pre=4并不是第一个节点，head才是。
    t->next = tail;
    if(t == head) return pre;
    else{
        hs->next = pre;
        return head;
    }
}

发表于 2020-07-04 15:35:51 回复(0)

C/C++

别搁那忽悠人了

list_node * reverse_list(list_node * head, int L, int R)
{
    //////在下面完成代码
    list_node* pre = head;
    list_node* time = NULL;
    list_node* last = head;
    list_node* curr = head;
    list_node* start = NULL;
    list_node* next = head;
    //调整指针位置
    for (int i = 1;i < L;i++){
         curr = curr->next;

    }
    start = curr;
    start->next = curr->next;
    start->val = curr->val;

    for (int i = 1;i < L - 1;i++){
        pre = pre->next;
    }

    for (int i = 0;i <= R - L;i++){
        next = curr->next;
        curr->next = time;
        time = curr;
        curr = next;

    }

    pre->next = time;
    start->next = next;
    return head;

}

发表于 2020-03-30 17:46:08 回复(0)

明月知何人

list_node* reverse_list(list_node* head, list_node * last, int k) {
    list_node* prev = last;
    list_node* cur = head;
    while(k--) {
        list_node* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
} 

list_node * reverse_list(list_node * head, int L, int R)
{
    //////在下面完成代码
    list_node* dummy = new list_node();
    dummy->next = head;
    list_node* p = dummy;
    for(int i = 0; i < L-1; ++i) {
        p = p->next;
    }
    list_node* q = dummy;
    for(int i = 0; i < R+1; ++i) {
        q = q->next;
    }
    p->next = reverse_list(p->next, q, R-L+1);

    list_node* ret = dummy->next;
    dummy->next = NULL;
    delete dummy;
    return ret;
}

发表于 2020-01-17 21:02:00 回复(0)

EVANnnn1996

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static class Node {

        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
    
    public static Node reversePart(Node head, int from, int to) {
        Node node1 = head;
        Node begin = null;
        Node end = null;
        int len = 0;
        while (node1 != null) {
            len++;
            // 找到反转部分的前一个结点
            begin = len == from - 1 ? node1 : begin;
            // 找到反转部分的后一个结点
            end = len == to + 1 ? node1 : end;
            node1 = node1.next;
        }
        if (from > to || from < 1 || to > len) {
            return head;
        }
        node1 = begin == null ? head : begin.next;
        Node node2 = node1.next;
        node1.next = end;
        Node next = null;
        while (node2 != end) {
            next = node2.next;
            node2.next = node1;
            node1 = node2;
            node2 = next;
        }
        if (begin != null) {
            begin.next = node1;
            return head;
        } else {
            return node1;
        }
    }

    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.value +" ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static Node listGenerator(int length, String[] numbers) {
        Node head = new Node(Integer.parseInt(numbers[0]));
        Node cur = head;
        for (int i = 1; i < length; i++) {
            cur.next = new Node(Integer.parseInt(numbers[i]));
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        String[] numbers = bufferedReader.readLine().split(" ");
        String[] parameters = bufferedReader.readLine().split(" ");
        int L = Integer.parseInt(parameters[0]);
        int R = Integer.parseInt(parameters[1]);
        Node head = listGenerator(n, numbers);
        head = reversePart(head, L, R);
        printList(head);
    }
}

发表于 2019-12-25 16:20:06 回复(0)

onedayday

//#include <bits/stdc++.h>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<list>
#include<map>
using namespace std;
using namespace std;

struct ListNode{
    int val;
    struct ListNode * next;
};

ListNode * input_list(void)
{
    int n, val;
    ListNode * phead = new ListNode();
    ListNode * cur_pnode = phead;
    cin >> n;
    for (int i = 1; i <= n; ++i) {

        cin >> val;
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            ListNode * new_pnode = new ListNode();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}

ListNode * reverse_list(ListNode * pHead, int m, int n)
{

    //////在下面完成代码
    {
        int count = 1; //计数
        ListNode* p = pHead;//M节点之前的指针不变量
        while (count <= m - 2)
        {
            p = p->next;
            count++;
        }
        ListNode *Pre = NULL;

        ListNode *Now = p->next;

        ListNode *END = p->next; //不变量
        if (m == 0)
        {
        Now = p;
        END = p;
        n = n + 1;
        }

        while (count <= n)
        {
            ListNode *NEXT = Now->next;
            Now->next = Pre;
            Pre = Now;
            Now = NEXT;
            count++;

        }
        if (m == 0)
        {
            pHead = Pre;
        }

        p->next = Pre;
        END->next = Now;


    }
    return pHead;

}

void print_list(ListNode * head)
{
    while (head != NULL) {

        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main()
{
    int L, R;
    ListNode * head = input_list();
    cin >> L >> R;

    ListNode * new_head = reverse_list(head, L-1, R-1);
    print_list(new_head);
    system("pause");
    return 0;
}

发表于 2019-08-22 21:51:24 回复(0)

反转部分单向链表

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题