Insert into a Cyclic Sorted List

2022. 1. 30. 23:38· 자료구조 알고리즘/코딩테스트

 Insert into a Cyclic Sorted List

내가 푼 것

넘 조잡해요 ㅠ

변수를 더 안썼다는 것에 의미를 조금 부여하고,

생성자 활용해서 next 추가한 것을 베스트 답안을 참고해서 보완해야되겠다. -> 주어진 것 잘 활용하기..

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
    }

    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
*/

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head) {
            Node* node = new Node(insertVal);
            node->next = node;
            return node;
        } else {
            Node* temp = head;
            while (1) {
                if (head->val < head->next->val) {
                    if (head->val <= insertVal && insertVal <= head->next->val)
                        break;
                }
                else if (head->val > head->next->val) {
                    if (head->next->val <= insertVal && insertVal <= head->val)
                        if (head->val < head->next->next->val)
                            break;
                    if (head->next->val > insertVal && insertVal < head->val)
                        break;
                    if (head->val < insertVal && insertVal > head->next->val)
                        break;
                } else if (head->val == head->next->val && head->next->val == head->next->next->val) {
                    break;
                }
                head = head->next;
            }

            Node* node = new Node(insertVal);
            node->next = head->next;
            head->next = node;

            if (!node->next)
                node->next = temp;
            return temp;
        }
    }
};

 

베스트

class Solution {
public:
  Node * insert(Node * head, int insertVal) {
    if (NULL == head) {
      auto newNode = new Node(insertVal);
      newNode->next = newNode;
      return newNode;
    }
    
    auto cur = head, next = head->next;
    while (head != next) {
      if (next->val >= cur->val) {
        if (insertVal >= cur->val && insertVal <= next->val) {
          cur->next = new Node(insertVal, next);
          return head;
        }
      } else if (insertVal >= cur->val || insertVal <= next->val) {
        cur->next = new Node(insertVal, next);
        return head;
      }
      
      cur = next;
      next = cur->next;
    }
    
    cur->next = new Node(insertVal, head);
    return head;
  }
};
class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        Node* node = new Node(insertVal);
        node->next = node;
        if(!head) return node;
        
        Node *p = head, *H = NULL, *T = NULL;
        do
        {
            if(p->val > p->next->val)
            {
                H = p->next;
                T = p;
                break;
            }
            p = p->next;
        }while(p != head);
        
        if(H == NULL)
        {
            // all number in the list are same value, insert any where
            node->next = head->next;
            head->next = node;
            return head;
        }
        
        if(insertVal <= H->val || insertVal >= T->val)
        {
            // insert after T
            node->next = T->next;
            T->next = node;
            return head;
        }
        
        while(H != T)
        {
            if(H->val <= insertVal && insertVal <= H->next->val)
            {
                // insert after H
                node->next = H->next;
                H->next = node;
                break;
            }
            H = H->next;
        }
        return head;
    }
};
728x90
반응형

'자료구조 알고리즘 > 코딩테스트' 카테고리의 다른 글

77484 로또의 최고 순위와 최저 순위  (0) 2022.02.03
92334 신고 결과 받기  (0) 2022.02.02
[다시예정] Flatten a Multilevel Doubly Linked List  (0) 2022.01.30
Add Two Numbers  (0) 2022.01.28
Merge Two Sorted Lists  (0) 2022.01.28
'자료구조 알고리즘/코딩테스트' 카테고리의 다른 글
  • 77484 로또의 최고 순위와 최저 순위
  • 92334 신고 결과 받기
  • [다시예정] Flatten a Multilevel Doubly Linked List
  • Add Two Numbers
내공얌냠
내공얌냠
내공냠냠
내공얌냠
내공냠냠
내공얌냠
전체
오늘
어제
  • 분류 전체보기 (254)
    • 개발 (113)
      • mediapipe (16)
      • insightface (5)
      • JongjuAR (3)
    • 자료구조 알고리즘 (79)
      • 코딩테스트 (64)
      • 이론 (15)
    • 공부 (7)
      • 단행본 (7)
      • 튜토리얼 (19)
      • 논문 (15)
      • 복기 (5)
    • 참여 (5)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

인기 글

태그

  • python telegrambot
  • mediapipe translate
  • vscode 스프링 설치
  • 컴퓨터 비전 책 추천
  • flutter
  • 미디어파이프
  • flutter 행사
  • mediapipe
  • speaker adaptation tts
  • 플러터
  • 플러터 튜토리얼
  • 구글 미디어파이프
  • postgresql 재설치
  • 머신러닝이란
  • git tutorial
  • flutter tutorial
  • torchscript vs onnx vs tensorrt
  • 깃 튜토리얼
  • 컴퓨터 비전
  • 컴퓨터 비전 기초
  • flutter conference
  • flutter 행사 후기
  • 딥러닝 기반 음성인식 기초
  • google mediapipe
  • kubeflow설치안됨
  • ios google places api
  • 음성인식 기초
  • 음성인식 튜토리얼
  • kubeflow설치가이드
  • postgresql install in mac

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
내공얌냠
Insert into a Cyclic Sorted List
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.