###### tags: `Week_1`, `Linked List`

# Linked List

## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)

harry:

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} list1
# @param {ListNode} list2
# @return {ListNode}
def merge_two_lists(list1, list2)
  p1 = list1
  p2 = list2
  head = ListNode.new
  p_ans = head
  
  while p1 || p2
    if p1.nil? || p2.nil?
      head.next = p1 ? p1 : p2
      break
    end
    
    if p1.val <= p2.val
      chosen = p1
      p1 = p1.next
    else
      chosen = p2
      p2 = p2.next
    end
      
    head.next = ListNode.new(chosen.val)
    head = head.next
  end
  
  p_ans.next
end

sam

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        root=ptr=ListNode()
        head1=list1
        head2=list2
        
        while head1 and head2:
            if head1.val > head2.val:
                ptr.next = ListNode(head2.val)
                head2 = head2.next
            else:
                ptr.next = ListNode(head1.val)
                head1 = head1.next
            ptr = ptr.next
        
        ptr.next = head1 or head2

        return root.next

## [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)

harry:

def reverse_list(head)
  return head if head.nil?
  
  pt = ListNode.new(0, head)
  stack = []
  
  stack.push(pt) while (pt = pt.next)
  ans = node = stack.pop
  node = node.next while (node.next = stack.pop)
    
  ans
end

harry(recursive):

def reverse_list(head)
  return head if head.nil? || head.next.nil?
  
  original_head = head
  new_head = reverse_two_nodes(head)
  original_head.next = nil
  new_head
end

def reverse_two_nodes(head)
  new_head =  if head.next.next.nil?
                head.next
              else
                reverse_two_nodes(head.next)
              end
  head.next.next = head
  new_head
end

Sam:

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        while head != None:
            temp = head.next
            head.next = prev
            prev = head
            head = temp
        return prev

Beny:

public ListNode ReverseList(ListNode head) {    
        ListNode ptr = head;   
        List<int> list =new List<int>();
        while(ptr != null){            
            list.Add(ptr.val);
            ptr = ptr.next;
        }
        ListNode result = new ListNode();  
        ListNode ptr1 = result;
        for(int i = list.Count-1; i > -1; i--){
            ptr1.next = new ListNode();
            ptr1 = ptr1.next;
            ptr1.val = list[i];           
        }       
        return result.next;
    }

## [876. Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list)
harry:

def middle_node(head)
  return head if head.next.nil?

  node = head
  s = 1
  s += 1 while node = node.next

  mid = (s / 2).ceil
  node = head
  0.upto(mid - 1) do
    node = node.next
  end
  node
end

# use cycle-like
def middle_node(head)
  slow = fast = head
  while fast.next&.next
    slow = slow.next
    fast = fast.next.next
  end
  if fast.next
    slow.next
  else
    slow
  end
end

Sam:

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        temp_list = []
        
        while head != None:
            temp_list.append(head)
            head = head.next
            
        if len(temp_list) == 1:
            return temp_list[0]
        else:
            return temp_list[len(temp_list) // 2]

# OP. 2 pointer
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        temp_list = []
        
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

# Because one of the prob. condition is "return second position if the linked list has two middle points."

beny:

public class Solution {
    public ListNode MiddleNode(ListNode head) {
        ListNode root = head;    
        ListNode ptr = head;
        ListNode result = head;
        bool go = false;
        while(ptr != null){
            if(go){
                ptr = ptr.next;
                result = result.next;
                go = false;
            }else{
                ptr = ptr.next;
                go = true;
            }                                  
        }    
        return result;
    }
}

## [142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii)
harry:

def detectCycle(head)
  return if head.nil?
  return head if head.next&.next == head
  
  slow = fast = head
  has_cycle = false
  
  while fast.next&.next
    slow = slow.next
    fast = fast.next.next
    if slow == fast
      has_cycle = true
      break
    end
  end

  if has_cycle
    begin
      head = head.next
      fast = fast.next
    end while head != fast
    fast
  end
end

Sam:
* Simple way: record every node in hash map & check if exist.
* Advanded way: Floyd cycle detection.

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return None

        slow=fast=head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        
        if fast != slow:
            return None

        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        
        return slow

beny:

public class Solution {
    public ListNode DetectCycle(ListNode head) {
        ListNode root = head;
        ListNode result = root;
        Dictionary <ListNode,ListNode> resultMap = new Dictionary <ListNode,ListNode>();
        while(result != null){            
            if(!resultMap.ContainsKey(result)){
                resultMap.Add(result,result);
                result = result.next;
            }else{
                return(resultMap[result]);
            }            
        }
        return null;
    }
}