Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Method 1: Using STACK

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null)
        {
            return head;
        }
        
        Stack<ListNode> st = new Stack<ListNode>();
        var tempHead = head;
        while(tempHead.next != null)
        {
            st.Push(tempHead);
            tempHead = tempHead.next;
        }
        
        head = tempHead;
        while(st.Count > 0)
        {
            tempHead.next = st.Pop();
            tempHead = tempHead.next;
        }
        tempHead.next = null;
        return head;
    }
}

Method 2: Using Previous, Next and Current Pointers

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null)
        {
            return head;
        }  
        
        ListNode cNode = head, nNode = head, pNode = null;
        
        while(cNode != null)
        {
            nNode = cNode.next;
            cNode.next = pNode;        
            pNode = cNode;
            cNode = nNode;
        }
        
        return pNode;
    }
}

Method 3 – Using a new list (Not using extra space just swapping references of Nodes)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null) return head;
        
        ListNode tempHead = null;
        ListNode temp = head;
        while(temp != null)
        {
            var temp1 = temp.next;
            temp.next = tempHead;
            tempHead = temp;
            temp = temp1;
        }
        
        return tempHead;
    }
}

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

public class Solution
    {
        public int LengthOfLongestSubstring(string s)
        {
            if (string.IsNullOrEmpty(s))
            {
                return 0;
            }

            var dict = new Dictionary<char, int>();
            int longestSubstringLength = 0, start = 0;
            for (int i = 0; i < s.Length; ++i)
            {
                if (!dict.ContainsKey(s[i]))
                {
                    dict.Add(s[i], i);
                }
                else
                {
                    while (start != dict[s[i]])
                    {
                        dict.Remove(s[start]);
                        start++;
                    }
                    start++;
                    dict[s[i]] = i;
                }

                longestSubstringLength = longestSubstringLength > (i - start) ? longestSubstringLength : (i - start);
            }

            return longestSubstringLength + 1;
        }
    }