2개의 배열된 연결리스트 합치기

合并两个排序的链表

Recursisve way

O(m+n) p1, p2가 각각의 리스트를 하나씩 체크

function Merge(pHead1, pHead2)
{
   if(!pHead1) return pHead2;
   if(!pHead2) return pHead1;

  	// while x
   if(pHead1.val <= pHead2.val) {
       pHead1.next = Merge(pHead1.next, pHead2);
       return pHead1;
   }
   else {
       pHead2.next = Merge(pHead1, pHead2.next);
       return pHead2;
   }
  // 남은거 이미 딸려있어서 처리할 필요없어
}

Iterative way

dummy = new Node
curr = dummy

시간 복잡도 O(m+n)
공간 복잡도 O(1)

// iterative
function merge(h1, h2) {
  let dummy = new Node(null);
  let curr = dummy;
  let p1 = h1, p2 = h2; // head는 건들이지 말자 (그냥 h1, h2써도 됌)
  // && 둘다 존재할때 비교할수 있음
  while(p1 && p2) {
    if(p1.value >= p2.value) {
      curr.next = p1;
      p1 = p1.next;
      curr = p1;
    }
    else {
      curr.next = p2;
      p2 = p2.next;
      curr = p2;
    }
  }
  // 마지막 남은 하나
  if(p1) curr.next = p1;
  if(p2) curr.next = p2;
  return dummy.next;
}

순환있는지 확인

判断链表中是否有环
노드마다 isVisited로 방문한 곳을 표시하고, 재방문하면 순환있음

function hasCycle( head ) {
   while(head) {
        if(head.isVisited) return true; // 재방문 순환함
        head.isVisited = true; // 처음방문
        head = head.next; // 다음 노드 이동   
    }
}

---

뒤에서 k번째 노드찾기

链表中倒数最后k个结点

array

array에 넣고 바로 arr[arr.length-k]로 찾기
공간 O(n)

function FindKthToTail( pHead ,  k ) {
    let arr = [];
    while(pHead) {
        arr.push(pHead);
        pHead = pHead.next;
    }
    // k번째가 없을때
    if(arr.length < k) return null;
    return arr[arr.length - k];
} 

---

2개의 리스트에서 첫 공통노드 구하기

두개를 계속 next로 이동시키는데, 더이상 없으면 서로의 헤더로 이동해서 다시 이동. 계속 반복하다보면 그 둘은 한곳에서 만난다.

function FindFirstCommonNode(pHead1, pHead2)
{
    if(!pHead1 || !pHead2) return null;
    let p1 = pHead1;
    let p2 = pHead2;
	// 둘이 만나기 전까지 계속 이동
    while(p1 !== p2) {
        // 계속 다음으로 넘어가는데, 다음이 없으면 다른 리스트의 헤더로 이동
        p1 = p1 ? p1.next : pHead2;
        p2 = p2 ? p2.next : pHead1;
    }
    return p1; // or p2
}

대칭되는 리스트인지 확인

判断一个链表是否为回文结构

주의
str으로 비교하면 {-401261,-449050,-456674,-456674,-449050,-401261} 이런 부호가 있을때 split 문제 있음

function isPail( head ) {
    if(!head) return null;
    let arr = [];
    let revArr = [];

    while(head) {
        arr.push(head.val);
        head = head.next;
    }
    revArr = [...arr].reverse();
    return arr.join('') === revArr.join('');
}

정렬된 리스트에서 중복제거하기

• 생각
  curr.val === head.val 중복할땐 curr움직이지 않고,
  curr.next = head.next 하고 head = head.next 한칸 이동해서,
  원래 curr와 새로운 head를 다시 비교.
• 주의 {1,1,1}

function deleteDuplicates( head ) {
    // write code here
    if(!head) return null;
    let dummy = new ListNode(-1);
    dummy.next = head;
    let curr = dummy;

    while(head) {
        if(curr.val === head.val) {
            curr.next = head.next;
            // curr = curr.next;
            head = head.next; //
        }
        else {
            curr = curr.next;
            head = head.next;
        }
    }
    return dummy.next;
}```

---
# 중간지점 찾기
leetcode 876
문제 : 주어진 LinkedList의 중간 node를 찾아서 return하여라 
예제1 : 1→3→5→7→9  ,  output : 5→7→9 \
예제2 : 1→2→3→4 ,   output : 3→4
- 중간이 노드면 그 노드를 반환
- 노드가 아니면 한칸 뒤의 노드를 반환

## 1) index
time O(n), space O(1) ?
한번 돌아서 전체 길이를 구한뒤, 반틈 만큼 다시 이동
>```js
function indexWay(head) {
  if (!head) return null;
  if (!head.next) return head;
  let totalCount = 0;
  let curr = head;
  while (curr) {
    totalCount++;
    curr = curr.next;
  }
  let mid = Math.floor(totalCount / 2);
  curr = head;
  for (let i = 0; i < mid; i++) {
    curr = curr.next;
  }
  // while (mid > 0) {
  //   curr = curr.next;
  //   mid--;
  // }
  return curr;
}```

## 2) array
한번 돌면서 노드들을 배열에 넣은뒤 arr.length를 이용해서 arr[length/2]로 한번에 찾는다
시간, 공간: O(n) 각각의 노드를 array에 넣는 시간, 공간

>```js
function arrayWay(head) {
  const arr = [];
  let curr = head;
  while (curr) {
    arr.push(curr);
    curr = curr.next;
  }
  return arr[Math.floor(arr.length / 2)];
}

3) fast, slow

한번만 순회하고 찾기
One pass + 공간이 O(1)으로 푸는 법

function fastSlow(head) {
  let fast = head,
    slow = head;
  while (fast) {
    if (fast.next) {
      fast = fast.next.next;
      slow = slow.next;
    } else {
      break;
    }
  }
  return slow;
}