Reverse Linked List II(Linked List)

 

 

https://leetcode.com/problems/reverse-linked-list-ii/description/

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

 

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

 

Follow up: Could you do it in one pass?

 

다시 돌아온 Daily Coding!

 

한 번 해보자!

 

1. Python

문제 이해를 잘 못 해서 틀렸다.

left~right 까지 reverse인데 , left / right swap으로 잘못 이해함 ㅠㅠ

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if not head or left==right : return head
        
        dummy = ListNode(0,head)
        prev = dummy
        idx = 1
        curr = head

        while idx < left :
            prev = curr
            curr = curr.next
            idx+=1

        temp_l = curr
        prev2 = None

        while idx <= right :
            temp = curr.next
            curr.next = prev2
            prev2 = curr
            curr = temp
            idx += 1

        prev.next = prev2
        temp_l.next = curr

        return dummy.next

 

Linkedlist는 C로도 풀 수 있어야 한다.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    if(!head || left==right) return head;

    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    
    struct ListNode* temp_left = head;
    struct ListNode* prev = dummy;
    int idx = 1;

    while(idx<left){
        prev = temp_left;
        temp_left = temp_left -> next;
        idx++;
    }

    struct ListNode* curr = temp_left;
    struct ListNode* prev2 = NULL;
    while(idx<=right){
        struct ListNode* nxt = curr->next;
        curr->next = prev2;
        prev2 = curr;
        curr = nxt;
        idx++;
    }
    temp_left -> next = curr;
    prev->next = prev2;
    return dummy->next;
}